Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Minimization of Systemic Risk for Directed Network Using Genetic Algorithm Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

A Fast ILP-Based Heuristic for the Robust Design of Body Wireless Sensor Networks

verfasst von : Fabio D’Andreagiovanni, Antonella Nardin, Enrico Natalizio

Erschienen in: Applications of Evolutionary Computation

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We consider the problem of optimally designing a body wireless sensor network, while taking into account the uncertainty of data generation of biosensors. Since the related min-max robustness Integer Linear Programming (ILP) problem can be difficult to solve even for state-of-the-art commercial optimization solvers, we propose an original heuristic for its solution. The heuristic combines deterministic and probabilistic variable fixing strategies, guided by the information coming from strengthened linear relaxations of the ILP robust model, and includes a very large neighborhood search for reparation and improvement of generated solutions, formulated as an ILP problem solved exactly. Computational tests on realistic instances show that our heuristic finds solutions of much higher quality than a state-of-the-art solver and than an effective benchmark heuristic.

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 Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks
Nächstes Kapitel Lamarckian and Lifelong Memetic Search in Agent-Based Computing
Fußnoten
1
We note that we assume that each biosensor \(b \in B\) never acts as a receiver and only generates and transmits data. So we do not characterize the subsets \(B_r, B_s \subseteq B\) of biosensors within the range of a relay r or a sink s. Furthermore, we assume that each sink s never acts as a transmitter and only receives data. So we do not characterize the subsets \(B_s \subseteq B\), \(R_s \subseteq R\) of biosensors and relays within the range of a sink s.
 
Literatur
1.
Ko, J., Lu, C., Srivastava, M., Stankovic, J., Terzis, A., Welsh, M.: Wireless sensor networks for healthcare. Proc. IEEE 98, 1947–1960 (2007)CrossRef
2.
Chen, M., Gonzalez, S., Vasilakos, A., Cao, H., Leung, V.: Body area networks: a survey. Mob. Netw. Appl. 16, 171–193 (2010)CrossRef
3.
Mitra, U., Emken, A., Lee, S., Li, M., Rozgic, V., Thatte, G., Vatsangam, H., Zois, D., Annavaram, M., Narayanan, S., Spruijt-Metz, D., Sukhatme, G.: KNOWME: a case study in wireless body area sensor network design. IEEE Commun. Mag. 50, 116–125 (2012)CrossRef
4.
Guerriero, F., Violi, A., Natalizio, E., Loscri, V., Costanzo, C.: Modelling and solving optimal placement problems in wireless sensor networks. Appl. Math. Model. 35, 230–241 (2011)MathSciNetCrossRefMATH
5.
Natalizio, E., Loscri, V., Viterbo, E.: Optimal placement of wireless nodes for maximizing path lifetime. IEEE Commun. Lett. 12, 362–364 (2008)CrossRef
6.
Negra, R., Jemilia, I., Belghith, A.: Wireless body area networks: applications and technologies. Procedia Comput. Sci. 83, 1274–1281 (2016)CrossRef
7.
D’Andreagiovanni, F.: Revisiting wireless network jamming by SIR-based considerations and multiband robust optimization. Optim. Lett. 9, 1495–1510 (2015)MathSciNetCrossRefMATH
8.
D’Andreagiovanni, F., Mannino, C., Sassano, A.: GUB covers and power-indexed formulations for wireless network design. Manag. Sci. 59, 142–156 (2013)CrossRef
9.
Gendron, B., Scutellà, M., Garroppo, R., Nencioni, G., Tavanti, L.: A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks. Eur. J. Oper. Res. 255, 151–162 (2016)MathSciNetCrossRefMATH
10.
Elias, J.: Optimal design of energy-efficient and cost-effective wireless body area networks. Ad Hoc Netw. 13, 560–574 (2014)CrossRef
11.
Tsouri, G., Prieto, A., Argade, N.: On increasing network lifetime in body area networks using global routing with energy consumption balancing. Sensors 12, 13088–13108 (2012)CrossRef
12.
Yousaf, S., Javaid, N., Khan, Z., Qasim, U., Imran, M., Iftikhar, M.: Incremental relay based cooperative communication in wireless body area networks. Procedia Comp. Sci. 52, 552–559 (2015)CrossRef
13.
D’Andreagiovanni, F., Nardin, A.: Towards the fast and robust optimal design of wireless body area networks. Appl. Soft Comput. 37, 971–982 (2015)CrossRef
14.
Braem, B., Latre, B., Moerman, I., Blondia, C., Reusens, E., Joseph, W., Martens, L., Demeester, P.: The need for cooperation and relaying in short-range high path loss sensor networks. In: SENSORCOMM 2007, pp. 566–571 (2007)
15.
Bertsekas, D.: Network Optimization: Continuous and Discrete Models. Athena Scientific, Belmont (1998)MATH
16.
D’Andreagiovanni, F., Krolikowski, J., Pulaj, J.: A fast hybrid primal heuristic for multiband robust capacitated network design with multiple time periods. Appl. Soft Comput. 26, 497–507 (2015)CrossRef
17.
Bauschert, T., Büsing, C., D’Andreagiovanni, F., Koster, A.M.C.A., Kutschka, M., Steglich, U.: Network planning under demand uncertainty with robust optimization. IEEE Commun. Mag. 52, 178–185 (2014)CrossRef
18.
Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Springer, Heidelberg (2009)CrossRefMATH
19.
Büsing, C., D’Andreagiovanni, F.: New results about multi-band uncertainty in robust optimization. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 63–74. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-30850-5_​7 CrossRef
20.
Aissi, H., Bazgan, C., Vanderpooten, D.: Min-max and min-max regret versions of combinatorial optimization problems. Eur. J. Oper. Res. 197, 427–438 (2009)MathSciNetCrossRefMATH
21.
Furini, F., Iori, M., Martello, S., Yagiura, M.: Heuristic and exact algorithms for the interval minmax regret knapsack problem. INFORMS J. Comput. 27, 392–405 (2015)MathSciNetCrossRefMATH
22.
23.
Maniezzo, V.: Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. INFORMS J. Comp. 11, 358–369 (1999)MathSciNetCrossRefMATH
24.
D’Andreagiovanni, F., Krolikowski, J., Pulaj, J.: A hybrid primal heuristic for robust multiperiod network design. In: Esparcia-Alcázar, A.I., Mora, A.M. (eds.) EvoApplications 2014. LNCS, vol. 8602, pp. 15–26. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-45523-4_​2
25.
Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B 26, 29–41 (1996)CrossRef
26.
Gambardella, L.M., Montemanni, R., Weyland, D.: Coupling ant colony systems with strong local searches. Eur. J. Oper. Res. 220, 831–843 (2012)MathSciNetCrossRefMATH
27.
Blum, C.: Ant colony optimization: introduction and recent trends. Phys. Life Rev. 2, 353–373 (2005)CrossRef
28.
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)CrossRefMATH
29.
Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102, 71–90 (2005)MathSciNetCrossRefMATH
30.
D’Andreagiovanni, F.: On improving the capacity of solving large-scale wireless network design problems by genetic algorithms. In: Chio, C., et al. (eds.) EvoApplications 2011. LNCS, vol. 6625, pp. 11–20. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-20520-0_​2 CrossRef
31.
Dely, P., D’Andreagiovanni, F., Kassler, A.: Fair optimization of mesh-connected WLAN hotspots. Wirel. Commun. Mob. Com. 15, 924–946 (2015)CrossRef
32.
Bley, A., D’Andreagiovanni, F., Karch, D.: WDM fiber replacement scheduling. Electron. Notes Discret. Math. 41, 189–196 (2013)CrossRef
33.
D’Andreagiovanni, F., Mannino, C., Sassano, A.: Negative cycle separation in wireless network design. In: Pahl, J., Reiners, T., Voß, S. (eds.) INOC 2011. LNCS, vol. 6701, pp. 51–56. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-21527-8_​7 CrossRef
34.
Zakrzewska, A., D’Andreagiovanni, F., Ruepp, S., Berger, M.: Biobjective optimization of radio access technology selection and resource allocation in heterogeneous wireless networks. In: 2013 11th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), pp. 652–658. IEEE (2013)
35.
D’Andreagiovanni, F., Caire, G.: An unconventional clustering problem: user service profile optimization. In: 2016 IEEE International Symposium on Information Theory (ISIT). IEEE Xplore, Piscataway. IEEE (2016). doi:10.​1109/​ISIT.​2016.​7541420
Metadaten
Titel
A Fast ILP-Based Heuristic for the Robust Design of Body Wireless Sensor Networks
verfasst von
Fabio D’Andreagiovanni
Antonella Nardin
Enrico Natalizio
Copyright-Jahr
2017
Buch
Applications of Evolutionary Computation

Print ISBN: 978-3-319-55848-6

Electronic ISBN: 978-3-319-55849-3

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-55849-3_16

Premium Partner

    Bildnachweise