nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Constructive Heuristics for Min-Power Bounded-Hops Symmetric Connectivity Problem

verfasst von : Roman Plotnikov, Adil Erzin

Erschienen in: Mathematical Optimization Theory and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider a problem of constructing an energy-efficient bounded diameter communication spanning tree when the vertices are located on a plane, and the energy required to transmit a message between a pair of vertices is proportional to the squared distance between them. For this NP-hard problem, we have developed several approximate heuristic algorithms. The results of a posteriori analysis of solutions constructed by the proposed algorithms are presented.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Net Present Value Maximization in Inventory Management System

Nächstes Kapitel Identification of the Optimal Set of Informative Features for the Problem of Separating of Mixed Production Batch of Semiconductor Devices for the Space Industry

Nur mit Berechtigung zugänglich

Rappaport, T.S.: Wireless Communications: Principles and Practices. Prentice Hall, Upper Saddle River (1996)

Clementi, A.E.F., Penna, P., Silvestri, R.: Hardness results for the power range assignment problem in packet radio networks. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) APPROX/RANDOM -1999. LNCS, vol. 1671, pp. 197–208. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-540-48413-4_21CrossRef

Kirousis, L.M., Kranakis, E., Krizanc, D., Pelc, A.: Power consumption in packet radio networks. Theore. Comput. Sci. 243(1–2), 289–305 (2000)MathSciNetCrossRef

Călinescu, G., Măndoiu, I.I., Zelikovsky, A.: Symmetric connectivity with minimum power consumption in radio networks. In: Baeza-Yates, R., Montanari, U., Santoro, N. (eds.) Foundations of Information Technology in the Era of Network and Mobile Computing. ITIFIP, vol. 96, pp. 119–130. Springer, Boston, MA (2002). https://doi.org/10.1007/978-0-387-35608-2_11CrossRef

Cheng, X., Narahari, B., Simha, R., Cheng, M.X., Liu, D.: Strong minimum energy topology in wireless sensor networks: NP-completeness and heuristics. IEEE Trans. Mob. Comput. 2(3), 248–256 (2003)CrossRef

Chu, T., Nikolaidis, I.: Energy efficient broadcast in mobile ad hoc networks. In: Proceedings AD-HOC Networks and Wireless (2002)

Park, J., Sahni, S.: Power assignment for symmetric communication in wireless networks. In: Proceedings of the 11th IEEE Symposium on Computers and Communications (ISCC), Washington, pp. 591–596. IEEE Computer Society, Los Alamitos (2006)

Althaus, E., Calinescu, G., Mandoiu, I.I., Prasad, S.K., Tchervenski, N., Zelikovsky, A.: Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks. Wireless Netw. 12(3), 287–299 (2006)CrossRef

Erzin, A., Plotnikov, R., Shamardin, Y.: On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem. J. Appl. Ind. Math. 7, 142–152 (2013)MathSciNetCrossRef

10.

Wolf, S., Merz, P.: Iterated local search for minimum power symmetric connectivity in wireless networks. In: Cotta, C., Cowling, P. (eds.) EvoCOP 2009. LNCS, vol. 5482, pp. 192–203. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01009-5_17CrossRef

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)MathSciNetCrossRef

12.

Erzin, A., Mladenovic, N., Plotnikov, R.: Variable neighborhood search variants for Min-power symmetric connectivity problem. Comput. Oper. Res. 78, 557–563 (2017)MathSciNetCrossRef

13.

Plotnikov, R., Erzin, A., Mladenovic, N.: VNDS for the min-power symmetric connectivity. Optim. Lett. (2018). https://doi.org/10.1007/s11590-018-1324-0CrossRefMATH

14.

Clementi, A.E.F., Ferreira, A., Penna, P., Perennes, S., Silvestri, R.: The minimum range assignment problem on linear radio networks. In: Paterson, M.S. (ed.) ESA 2000. LNCS, vol. 1879, pp. 143–154. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45253-2_14CrossRef

15.

Calinescu, G., Kapoor, S., Sarwat, M.: Bounded-hops power assignment in ad hoc wireless networks. Discrete Appl. Math. 154(9), 1358–1371 (2006)MathSciNetCrossRef

16.

Carmi, P., Chaitman-Yerushalmi, L., Trabelsi, O.: On the bounded-hop range assignment problem. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 140–151. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21840-3_12CrossRef

17.

Clementi, A.E.F., Penna, P., Silvestri, R.: On the power assignment problem in radio networks. In: Electronic Colloquium on Computational Complexity (ECCC), (054) (2000)

18.

Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389–1401 (1957)CrossRef

19.

Julstrom, B.A.: Greedy heuristics for the bounded diameter minimum spanning tree problem. J. Exp. Algorithmics 14(1), 1–14 (2009)MathSciNetMATH

20.

Patvardhan, C., Prem Prakash, V., Srivastav, A.: Fast heuristics for large instances of the Euclidean bounded diameter minimum spanning tree problem. Informatica 39, 281–292 (2015)MathSciNet

21.

Nghia, N.D., Binh, H.T.T.: Heuristic Algorithms for Solving Bounded Diameter Minimum Spanning Tree Problem and Its Application to Genetic Algorithm Development, Greedy Algorithms, Witold Bednorz. IntechOpen (2008). https://doi.org/10.5772/6345

22.

Deo, N., Abdalla, A.: Computing a diameter-constrained minimum spanning tree in parallel. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol. 1767, pp. 17–31. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-46521-9_2CrossRef

23.

Gruber, M., Raidl, G.R.: A new 0–1 ILP approach for the bounded diameter minimum spanning tree problem. In: Proceedings of the 2nd International Network Optimization Conference (2005)

Titel: Constructive Heuristics for Min-Power Bounded-Hops Symmetric Connectivity Problem
verfasst von: Roman Plotnikov
Adil Erzin
Verlag: Springer International Publishing
Buch: Mathematical Optimization Theory and Operations Research
Print ISBN: 978-3-030-33393-5

Electronic ISBN: 978-3-030-33394-2

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-33394-2_31

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"