Skip to main content
Top

2017 | OriginalPaper | Chapter

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

Authors : Fabio D’Andreagiovanni, Antonella Nardin, Enrico Natalizio

Published in: Applications of Evolutionary Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

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!

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!

Footnotes
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.
 
Literature
1.
go back to reference Ko, J., Lu, C., Srivastava, M., Stankovic, J., Terzis, A., Welsh, M.: Wireless sensor networks for healthcare. Proc. IEEE 98, 1947–1960 (2007)CrossRef 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.
go back to reference Chen, M., Gonzalez, S., Vasilakos, A., Cao, H., Leung, V.: Body area networks: a survey. Mob. Netw. Appl. 16, 171–193 (2010)CrossRef Chen, M., Gonzalez, S., Vasilakos, A., Cao, H., Leung, V.: Body area networks: a survey. Mob. Netw. Appl. 16, 171–193 (2010)CrossRef
3.
go back to reference 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 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.
go back to reference 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 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.
go back to reference Natalizio, E., Loscri, V., Viterbo, E.: Optimal placement of wireless nodes for maximizing path lifetime. IEEE Commun. Lett. 12, 362–364 (2008)CrossRef Natalizio, E., Loscri, V., Viterbo, E.: Optimal placement of wireless nodes for maximizing path lifetime. IEEE Commun. Lett. 12, 362–364 (2008)CrossRef
6.
go back to reference Negra, R., Jemilia, I., Belghith, A.: Wireless body area networks: applications and technologies. Procedia Comput. Sci. 83, 1274–1281 (2016)CrossRef Negra, R., Jemilia, I., Belghith, A.: Wireless body area networks: applications and technologies. Procedia Comput. Sci. 83, 1274–1281 (2016)CrossRef
7.
go back to reference D’Andreagiovanni, F.: Revisiting wireless network jamming by SIR-based considerations and multiband robust optimization. Optim. Lett. 9, 1495–1510 (2015)MathSciNetCrossRefMATH D’Andreagiovanni, F.: Revisiting wireless network jamming by SIR-based considerations and multiband robust optimization. Optim. Lett. 9, 1495–1510 (2015)MathSciNetCrossRefMATH
8.
go back to reference D’Andreagiovanni, F., Mannino, C., Sassano, A.: GUB covers and power-indexed formulations for wireless network design. Manag. Sci. 59, 142–156 (2013)CrossRef 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.
go back to reference 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 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.
go back to reference Elias, J.: Optimal design of energy-efficient and cost-effective wireless body area networks. Ad Hoc Netw. 13, 560–574 (2014)CrossRef Elias, J.: Optimal design of energy-efficient and cost-effective wireless body area networks. Ad Hoc Netw. 13, 560–574 (2014)CrossRef
11.
go back to reference 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 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.
go back to reference 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 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.
go back to reference 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 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.
go back to reference 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) 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.
go back to reference Bertsekas, D.: Network Optimization: Continuous and Discrete Models. Athena Scientific, Belmont (1998)MATH Bertsekas, D.: Network Optimization: Continuous and Discrete Models. Athena Scientific, Belmont (1998)MATH
16.
go back to reference 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 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.
go back to reference 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 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.
go back to reference Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Springer, Heidelberg (2009)CrossRefMATH Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Springer, Heidelberg (2009)CrossRefMATH
19.
20.
go back to reference 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 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.
go back to reference 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 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
23.
go back to reference Maniezzo, V.: Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. INFORMS J. Comp. 11, 358–369 (1999)MathSciNetCrossRefMATH Maniezzo, V.: Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. INFORMS J. Comp. 11, 358–369 (1999)MathSciNetCrossRefMATH
24.
go back to reference 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 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.
go back to reference 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 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.
go back to reference Gambardella, L.M., Montemanni, R., Weyland, D.: Coupling ant colony systems with strong local searches. Eur. J. Oper. Res. 220, 831–843 (2012)MathSciNetCrossRefMATH 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.
go back to reference Blum, C.: Ant colony optimization: introduction and recent trends. Phys. Life Rev. 2, 353–373 (2005)CrossRef Blum, C.: Ant colony optimization: introduction and recent trends. Phys. Life Rev. 2, 353–373 (2005)CrossRef
28.
go back to reference Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)CrossRefMATH Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)CrossRefMATH
29.
go back to reference Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102, 71–90 (2005)MathSciNetCrossRefMATH Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102, 71–90 (2005)MathSciNetCrossRefMATH
30.
go back to reference 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 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.
go back to reference Dely, P., D’Andreagiovanni, F., Kassler, A.: Fair optimization of mesh-connected WLAN hotspots. Wirel. Commun. Mob. Com. 15, 924–946 (2015)CrossRef Dely, P., D’Andreagiovanni, F., Kassler, A.: Fair optimization of mesh-connected WLAN hotspots. Wirel. Commun. Mob. Com. 15, 924–946 (2015)CrossRef
32.
go back to reference Bley, A., D’Andreagiovanni, F., Karch, D.: WDM fiber replacement scheduling. Electron. Notes Discret. Math. 41, 189–196 (2013)CrossRef Bley, A., D’Andreagiovanni, F., Karch, D.: WDM fiber replacement scheduling. Electron. Notes Discret. Math. 41, 189–196 (2013)CrossRef
33.
go back to reference 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 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.
go back to reference 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) 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.
go back to reference 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 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
Metadata
Title
A Fast ILP-Based Heuristic for the Robust Design of Body Wireless Sensor Networks
Authors
Fabio D’Andreagiovanni
Antonella Nardin
Enrico Natalizio
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-55849-3_16

Premium Partner