Skip to main content
SpringerLink
Log in

The Accuracy of One Polynomial Algorithm for the Convergecast Scheduling Problem on a Square Grid with Rectangular Obstacles

  • Conference paper
  • First Online:
Book cover Learning and Intelligent Optimization (LION 12 2018)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11353))

Included in the following conference series:

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 to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. 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)

    Google Scholar 

  2. Cardei, M., Wu, J.: Energy-efficient coverage problems in wireless ad-hoc sensor networks. Comput. Commun. 29, 413–420 (2006)

    Article  Google Scholar 

  3. Carle, J., Simplot, D.: Energy-efficient area monitoring by sensor networks. IEEE Comput. 37, 40–46 (2004)

    Article  Google Scholar 

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

  5. 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)

    Google Scholar 

  6. 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)

    Google Scholar 

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

  8. 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)

    Article  MathSciNet  Google Scholar 

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

  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)

    Article  Google Scholar 

  11. Malhotra, B., Nikolaidis, I., Nascimento, M.A.: Aggregation convergecast scheduling in wireless sensor networks. Wirel. Netw. 17, 319–335 (2011)

    Article  Google Scholar 

  12. 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)

    Article  Google Scholar 

  13. 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)

    Article  Google Scholar 

  14. Wang, P., He, Y., Huang, L.: Near optimal scheduling of data aggregation in wireless sensor networks. Ad Hoc Netw. 11, 1287–1296 (2013)

    Article  Google Scholar 

  15. 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)

    Article  Google Scholar 

  16. Zalyubovskiy, V., Erzin, A., Astrakov, S., Choo, H.: Energy-efficient area coverage by sensors with adjustable ranges. Sensors 9, 2446–2460 (2009)

    Article  Google Scholar 

Download references

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

  1. Sobolev Institute of Mathematics, 4 Koptyug avenue, 630090, Novosibirsk, Russia

    Adil Erzin & Roman Plotnikov

  2. Novosibirsk State University, 1 Pirogova str, 630090, Novosibirsk, Russia

    Adil Erzin

Authors
  1. Adil Erzin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Roman Plotnikov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Adil Erzin .

Editor information

Editors and Affiliations

  1. University of Trento, Trento, Italy

    Roberto Battiti

  2. University of Trento, Trento, Italy

    Mauro Brunato

  3. Wilfrid Laurier University, Waterloo, ON, Canada

    Ilias Kotsireas

  4. University of Florida, Gainesville, FL, USA

    Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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)

Publish with us

Policies and ethics

Search

Navigation