Abstract
The problem of conflict-free data aggregation in an arbitrary graph is NP-hard. On a square unit grid, in each node of which a sensor is located, the problem is polynomially solvable. For the case when the graph is a regular triangular grid, the upper bound on the length of the schedule of conflict-free data aggregation was previously known. In this paper, the refined estimates are given for the length of the schedule of conflict-free data aggregation on a triangular grid, as well as polynomially solvable cases are found and algorithms for constructing optimal and approximate schedules are proposed.
A. Erzin thanks the Russian Foundation for Basic Research, grant 19–47–540007 and the program of fundamental scientific researches of the SB RAS, project 0314–2019–0014 (contribution: Sects. 1–3), and R. Plonikov thanks the Russian Science Foundation, grant 18–71–00084 (contribution: Sects. 4, 5), for financial support.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cheng, C.-T., Tse, C.K., Lau, F.C.M.: A delay-aware data collection network structure for wireless sensor networks. IEEE Sens. J. 11(3), 699–710 (2011)
De Souza, E., Nikolaidis, I.: An exploration of aggregation convergecast scheduling. Ad Hoc Netw. 11, 2391–2407 (2013)
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., Plotnikov, R.: Conflict-free data aggregation on a square grid when transmission distance is not less than 3. In: Fernández Anta, A., Jurdzinski, T., Mosteiro, M.A., Zhang, Y. (eds.) ALGOSENSORS 2017. LNCS, vol. 10718, pp. 141–154. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72751-6_11
Erzin, A., Plotnikov, R.: Using VNS for the optimal synthesis of the communication tree in wireless sensor networks. Electron. Notes Discrete Math. 47, 21–28 (2015)
Erzin, A., Plotnikov, R., Mladenovic, N.: Variable neighborhood search variants for min-power symmetric connectivity problem. Comput. Oper. Res. 78, 557–563 (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 (CSNDSP), no. 16. IEEE-Xplore, Prague (2016)
Gagnon, J., Narayanan, L.: Minimum latency aggregation scheduling in wireless sensor networks. In: 11th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pp. 152–168. Wroclaw, Poland (2014)
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)
Hansen, P., Kuplinsky, J., De Werra, D.: Mixed graph colorings. Math. Methods Oper. Res. 45, 145–160 (1997)
Incel, O.D., Ghosh, A., Krishnamachari, B., Chintalapudi, K.: Fast data collection in tree-based wireless sensor networks. IEEE Trans. Mobi. Comput. 11(1), 86–99 (2012)
Li, H., Hua, Q.-S., Wu, C., Lau, F.C.M.: Minimum-latency aggregation scheduling in wireless sensor networks under physical interference model. HKU CS Tech Report TR-2010-07 (2010). https://doi.org/10.1145/1868521.1868581
Malhotra, B., Nikolaidis, I., Nascimento, M.A.: Aggregation convergecast scheduling in wireless sensor networks. Wireless Netw. 17, 319–335 (2011)
Nguyen, T.D., Zalyubovskiy, V., Choo, H.: Efficient time latency of data aggregation based on neighboring dominators in WSNs. In: IEEE Globecom, pp. 6133827 (2011)
Plotnikov, R., Erzin, A., Mladenovic, N.: Variable neighborhood search-based heuristics for min-power symmetric connectivity problem in wireless networks. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 220–232. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44914-2_18
Plotnikov, R., Erzin, A., Zalyubovskiy, V.: Convergecast with unbounded number of channels. In: MATEC Web of Conferences, vol. 125, pp. 03001 (2017). https://doi.org/10.1051/matecconf/201712503001
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(4), 2446–2460 (2009)
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 Convergecast Scheduling Problem on a Regular Triangular Grid. In: Bykadorov, I., Strusevich, V., Tchemisova, T. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Communications in Computer and Information Science, vol 1090. Springer, Cham. https://doi.org/10.1007/978-3-030-33394-2_28
Download citation
DOI: https://doi.org/10.1007/978-3-030-33394-2_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-33393-5
Online ISBN: 978-3-030-33394-2
eBook Packages: Computer ScienceComputer Science (R0)