Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2018 | OriginalPaper | Buchkapitel

39. Optimization Problems, Models, and Heuristics in Wireless Sensor Networks

verfasst von: Vinicius Morais, Fernanda S. H. Souza, Geraldo R. Mateus

Erschienen in: Handbook of Heuristics

Verlag: Springer International Publishing

share
TEILEN

Abstract

This chapter provides an overview and a comprehensive discussion of problems, models, algorithms, and applications in a vast and growing literature of wireless sensor networks. Being a particular kind of ad hoc network, many power management and communication protocols may be designed specifically for those networks. The critical issues considered in these protocols are the objectives, the quality of communication, the energy consumption, and the network lifetime. Moreover, due to the large-scale aspect inherent in some applications, traditional exact solution approaches are not practical, so heuristics may be adopted instead. The chapter starts by introducing the main concepts in the design of WSN and a wide range of problems and applications. Basic formulations and algorithms are also discussed, together with their benefits and drawbacks.
Literatur
1.
Zurück zum Zitat Akyildiz I, Su W, Sankarasubramaniam Y, Cayirci E (2002) Wireless sensor networks: a survey. Comput Netw 38(4):393–422 CrossRef Akyildiz I, Su W, Sankarasubramaniam Y, Cayirci E (2002) Wireless sensor networks: a survey. Comput Netw 38(4):393–422 CrossRef
2.
Zurück zum Zitat Yick J, Mukherjee B, Ghosal D (2008) Wireless sensor network survey. Comput Netw 52(12):2292–2330 CrossRef Yick J, Mukherjee B, Ghosal D (2008) Wireless sensor network survey. Comput Netw 52(12):2292–2330 CrossRef
3.
Zurück zum Zitat Xu N (2002) A survey of sensor network applications. In: IEEE communications magazine electronics, robotics and automotive mechanics conference, Washington, DC, pp 102–114 Xu N (2002) A survey of sensor network applications. In: IEEE communications magazine electronics, robotics and automotive mechanics conference, Washington, DC, pp 102–114
4.
Zurück zum Zitat Arampatzis T, Lygeros J, Member S, Manesis S (2005) A survey of applications of wireless sensors and wireless sensor networks. In: Proceedings of the 13th Mediterranean conference on control and automation, Limassol, pp 719–724 Arampatzis T, Lygeros J, Member S, Manesis S (2005) A survey of applications of wireless sensors and wireless sensor networks. In: Proceedings of the 13th Mediterranean conference on control and automation, Limassol, pp 719–724
5.
Zurück zum Zitat Kuorilehto M, Hännikäinen M, Hämäläinen TD (2005) A survey of application distribution in wireless sensor networks. EURASIP J Wirel Commun Netw 2005:774–788 CrossRef Kuorilehto M, Hännikäinen M, Hämäläinen TD (2005) A survey of application distribution in wireless sensor networks. EURASIP J Wirel Commun Netw 2005:774–788 CrossRef
6.
Zurück zum Zitat Yoneki E, Bacon J (2005) A survey of wireless sensor network technologies: research trends and middleware’s role. Technical report UCAM-CL-TR-646, Computer Laboratory, University of Cambridge, Cambridge, UK Yoneki E, Bacon J (2005) A survey of wireless sensor network technologies: research trends and middleware’s role. Technical report UCAM-CL-TR-646, Computer Laboratory, University of Cambridge, Cambridge, UK
7.
Zurück zum Zitat Munir S, Ren B, Jiao W, Wang B, Xie D, Ma J (2007) Mobile wireless sensor network: architecture and enabling technologies for ubiquitous computing. In: 21st international conference on advanced information networking and applications workshops, 2007, AINAW’07, Niagara Falls, vol 2, pp 113–120 Munir S, Ren B, Jiao W, Wang B, Xie D, Ma J (2007) Mobile wireless sensor network: architecture and enabling technologies for ubiquitous computing. In: 21st international conference on advanced information networking and applications workshops, 2007, AINAW’07, Niagara Falls, vol 2, pp 113–120
8.
Zurück zum Zitat Khan MI, Gansterer WN, Haring G (2013) Static vs. mobile sink: the influence of basic parameters on energy efficiency in wireless sensor networks. Comput Commun 36:965–978 CrossRef Khan MI, Gansterer WN, Haring G (2013) Static vs. mobile sink: the influence of basic parameters on energy efficiency in wireless sensor networks. Comput Commun 36:965–978 CrossRef
9.
Zurück zum Zitat Anastasi G, Conti M, Di Francesco M, Passarella A (2009) Energy conservation in wireless sensor networks: a survey. Ad Hoc Netw 7:537–568 CrossRef Anastasi G, Conti M, Di Francesco M, Passarella A (2009) Energy conservation in wireless sensor networks: a survey. Ad Hoc Netw 7:537–568 CrossRef
10.
Zurück zum Zitat Kuhn F, Wattenhofer R, Zollinger A (2008) Ad hoc networks beyond unit disk graphs. Wirel Netw 14:715–729 CrossRef Kuhn F, Wattenhofer R, Zollinger A (2008) Ad hoc networks beyond unit disk graphs. Wirel Netw 14:715–729 CrossRef
11.
Zurück zum Zitat Al-Karaki JN, Kamal AE (2004) Routing techniques in wireless sensor networks: a survey. Wirel Commun 11:6–28 CrossRef Al-Karaki JN, Kamal AE (2004) Routing techniques in wireless sensor networks: a survey. Wirel Commun 11:6–28 CrossRef
12.
Zurück zum Zitat Langendoen K, Reijers N (2003) Distributed localization in wireless sensor networks: a quantitative comparison. Comput Netw 43:499–518 CrossRef Langendoen K, Reijers N (2003) Distributed localization in wireless sensor networks: a quantitative comparison. Comput Netw 43:499–518 CrossRef
13.
Zurück zum Zitat Madan R, Lall S (2006) Distributed algorithms for maximum lifetime routing in wireless sensor networks. IEEE Trans Wirel Commun 5:2185–2193 CrossRef Madan R, Lall S (2006) Distributed algorithms for maximum lifetime routing in wireless sensor networks. IEEE Trans Wirel Commun 5:2185–2193 CrossRef
14.
Zurück zum Zitat Kubisch M, Karl H, Wolisz A, Zhong LC, Rabaey J (2003) Distributed algorithms for transmission power control in wireless sensor networks. In: 2003 IEEE Wireless Communications and Networking, WCNC 2003, New Orleans, vol 1, pp 558–563 Kubisch M, Karl H, Wolisz A, Zhong LC, Rabaey J (2003) Distributed algorithms for transmission power control in wireless sensor networks. In: 2003 IEEE Wireless Communications and Networking, WCNC 2003, New Orleans, vol 1, pp 558–563
15.
Zurück zum Zitat Boukerche A, Oliveira HA, Nakamura EF, Loureiro AAF (2007) Localization systems for wireless sensor networks. IEEE Wirel Commun 14:6–12 CrossRef Boukerche A, Oliveira HA, Nakamura EF, Loureiro AAF (2007) Localization systems for wireless sensor networks. IEEE Wirel Commun 14:6–12 CrossRef
16.
Zurück zum Zitat Efrat A, Har-Peled S, Mitchell JSB (2005) Approximation algorithms for two optimal location problems in sensor networks. In: 2nd international conference on broadband networks, BroadNets 2005, Boston, vol 1, pp 714–723 Efrat A, Har-Peled S, Mitchell JSB (2005) Approximation algorithms for two optimal location problems in sensor networks. In: 2nd international conference on broadband networks, BroadNets 2005, Boston, vol 1, pp 714–723
17.
Zurück zum Zitat Basagni S, Carosi A, Melachrinoudis E, Petrioli C, Wang ZM (2008) Controlled sink mobility for prolonging wireless sensor networks lifetime. Wirel Netw 14(6):831–858 CrossRef Basagni S, Carosi A, Melachrinoudis E, Petrioli C, Wang ZM (2008) Controlled sink mobility for prolonging wireless sensor networks lifetime. Wirel Netw 14(6):831–858 CrossRef
18.
Zurück zum Zitat Wolsey LA (1998) Integer programming. Wiley-Interscience, New York MATH Wolsey LA (1998) Integer programming. Wiley-Interscience, New York MATH
19.
Zurück zum Zitat Nakamura F, Quintão F, Menezes G, Mateus G (2005) An optimal node scheduling for flat wireless sensor networks. Lect Notes Comput Sci 3420:475–482 CrossRef Nakamura F, Quintão F, Menezes G, Mateus G (2005) An optimal node scheduling for flat wireless sensor networks. Lect Notes Comput Sci 3420:475–482 CrossRef
20.
Zurück zum Zitat Jarray F (2013) A lagrangean-based heuristics for the target covering problem in wireless sensor network. Appl Math Model 37:6780–6785 MathSciNetCrossRef Jarray F (2013) A lagrangean-based heuristics for the target covering problem in wireless sensor network. Appl Math Model 37:6780–6785 MathSciNetCrossRef
21.
Zurück zum Zitat Castaño F, Bourreau E, Velasco N, Rossi A, Sevaux M (2015) Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks. Eur J Oper Res 241(1):28–38 MathSciNetCrossRef Castaño F, Bourreau E, Velasco N, Rossi A, Sevaux M (2015) Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks. Eur J Oper Res 241(1):28–38 MathSciNetCrossRef
22.
Zurück zum Zitat Lee J-H, Moon I (2014) Modeling and optimization of energy efficient routing in wireless sensor networks. Appl Math Model 38(7–8):2280–2289 MathSciNetCrossRef Lee J-H, Moon I (2014) Modeling and optimization of energy efficient routing in wireless sensor networks. Appl Math Model 38(7–8):2280–2289 MathSciNetCrossRef
23.
Zurück zum Zitat Valle CA, Martinez LC, da Cunha AS, Mateus GR (2011) Heuristic and exact algorithms for a min–max selective vehicle routing problem. Comput Oper Res 38(7):1054–1065 MathSciNetCrossRef Valle CA, Martinez LC, da Cunha AS, Mateus GR (2011) Heuristic and exact algorithms for a min–max selective vehicle routing problem. Comput Oper Res 38(7):1054–1065 MathSciNetCrossRef
24.
25.
Zurück zum Zitat Resende MG, Ribeiro CC (2005) Grasp with path-relinking: recent advances and applications. In: Ibaraki T, Nonobe K, Yagiura M (eds) Metaheuristics: progress as real problem solvers. Operations research/computer science interfaces series, vol 32. Springer, New York, pp 29–63 CrossRef Resende MG, Ribeiro CC (2005) Grasp with path-relinking: recent advances and applications. In: Ibaraki T, Nonobe K, Yagiura M (eds) Metaheuristics: progress as real problem solvers. Operations research/computer science interfaces series, vol 32. Springer, New York, pp 29–63 CrossRef
26.
27.
Zurück zum Zitat Lourenço HR, Martin OC, Stutzle T (2010) Iterated local search: framework and applications. In: Glover F, Kochenberger G, Hillier F (eds) Handbook of metaheuristics. International series in operations research and management science, vol 57, ch 12, 2nd edn. Springer, New York, pp 363–398 Lourenço HR, Martin OC, Stutzle T (2010) Iterated local search: framework and applications. In: Glover F, Kochenberger G, Hillier F (eds) Handbook of metaheuristics. International series in operations research and management science, vol 57, ch 12, 2nd edn. Springer, New York, pp 363–398
28.
Zurück zum Zitat Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13(5):533–549. Applications of integer programming Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13(5):533–549. Applications of integer programming
29.
Zurück zum Zitat Hansen P, Mladenović N (2001) Variable neighborhood search: principles and applications. Eur J Oper Res 130(3):449–467 MathSciNetCrossRef Hansen P, Mladenović N (2001) Variable neighborhood search: principles and applications. Eur J Oper Res 130(3):449–467 MathSciNetCrossRef
30.
Zurück zum Zitat Hansen P, Mladenović N (2001) Variable neighborhood search. In: Pardalos P, Resende M (eds) Handbook of applied optimization. Oxford University Press, New York MATH Hansen P, Mladenović N (2001) Variable neighborhood search. In: Pardalos P, Resende M (eds) Handbook of applied optimization. Oxford University Press, New York MATH
31.
Zurück zum Zitat Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 2nd edn. 1992 Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 2nd edn. 1992
32.
Zurück zum Zitat Moscato P (1999) Memetic algorithms: a short introduction. In: Corne D, Dorigo M, Glover F, Dasgupta D, Moscato P, Poli R, Price KV (eds) New ideas in optimization. McGraw-Hill Ltd., Maidenhead, pp 219–234 Moscato P (1999) Memetic algorithms: a short introduction. In: Corne D, Dorigo M, Glover F, Dasgupta D, Moscato P, Poli R, Price KV (eds) New ideas in optimization. McGraw-Hill Ltd., Maidenhead, pp 219–234
33.
34.
Zurück zum Zitat Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings IEEE international conference on neural networks, Perth, vol 4, pp 1942–1948 CrossRef Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings IEEE international conference on neural networks, Perth, vol 4, pp 1942–1948 CrossRef
35.
Zurück zum Zitat Glover F, Kochenberger GA (2003) Handbook of metaheuristics. Kluwer Academic Publishers, Boston CrossRef Glover F, Kochenberger GA (2003) Handbook of metaheuristics. Kluwer Academic Publishers, Boston CrossRef
36.
Zurück zum Zitat Nieberg T (2006) Independent and dominating sets in wireless communication graphs. Ph.D. thesis, University of Twente Nieberg T (2006) Independent and dominating sets in wireless communication graphs. Ph.D. thesis, University of Twente
37.
Zurück zum Zitat Ren H, Meng M-H, Chen X (2006) Investigating network optimization approaches in wireless sensor networks. In: International conference on intelligent robots and systems, Deajeon, pp 2015–2021 Ren H, Meng M-H, Chen X (2006) Investigating network optimization approaches in wireless sensor networks. In: International conference on intelligent robots and systems, Deajeon, pp 2015–2021
38.
Zurück zum Zitat Li J (2008) Optimization problems in wireless sensor and passive optical networks. Ph.D. thesis, The University of Melbourne Li J (2008) Optimization problems in wireless sensor and passive optical networks. Ph.D. thesis, The University of Melbourne
39.
Zurück zum Zitat Suomela J (2009) Optimisation problems in wireless sensor networks: local algorithms and local graphs. Ph.D. thesis, University of Helsinki Suomela J (2009) Optimisation problems in wireless sensor networks: local algorithms and local graphs. Ph.D. thesis, University of Helsinki
40.
Zurück zum Zitat Gogu A, Nace D, Dilo A, Meratnia N (2012) Review of optimization problems in wireless sensor networks. In: Hamilton Ortiz J (ed) Telecommunications networks – current status and future trends. InTech, Rijeka, pp 153–180 Gogu A, Nace D, Dilo A, Meratnia N (2012) Review of optimization problems in wireless sensor networks. In: Hamilton Ortiz J (ed) Telecommunications networks – current status and future trends. InTech, Rijeka, pp 153–180
41.
Zurück zum Zitat Molina G, Alba E (2011) Location discovery in wireless sensor networks using metaheuristics. Appl Soft Comput 11(1):1223–1240 CrossRef Molina G, Alba E (2011) Location discovery in wireless sensor networks using metaheuristics. Appl Soft Comput 11(1):1223–1240 CrossRef
42.
Zurück zum Zitat Shahrokhzadeh M, Haghighat AT, Mahmoudi F, Shahrokhzadeh B (2011) A heuristic method for wireless sensor network localization. In: Procedia computer science, vol 5. The 2nd international conference on ambient systems, networks and technologies (ANT-2011)/the 8th international conference on mobile web information systems (MobiWIS 2011). Elsevier, Niagara Falls, pp 812–819 Shahrokhzadeh M, Haghighat AT, Mahmoudi F, Shahrokhzadeh B (2011) A heuristic method for wireless sensor network localization. In: Procedia computer science, vol 5. The 2nd international conference on ambient systems, networks and technologies (ANT-2011)/the 8th international conference on mobile web information systems (MobiWIS 2011). Elsevier, Niagara Falls, pp 812–819
43.
Zurück zum Zitat Brazil M, Ras CJ, Thomas DA (2009) Deterministic deployment of wireless sensor networks. In: Proceedings of the world congress on engineering 2009, London, vol 1, p 863 Brazil M, Ras CJ, Thomas DA (2009) Deterministic deployment of wireless sensor networks. In: Proceedings of the world congress on engineering 2009, London, vol 1, p 863
44.
Zurück zum Zitat Sasikumar P, Vasudevan SK, Ramesh M (2010) Heuristic approaches with energy management for node placement in wireless sensor networks. Int J Comput Appl 1(37):34–736 Sasikumar P, Vasudevan SK, Ramesh M (2010) Heuristic approaches with energy management for node placement in wireless sensor networks. Int J Comput Appl 1(37):34–736
45.
Zurück zum Zitat Laszka A, Buttyán L, Szeszlér D (2013) Designing robust network topologies for wireless sensor networks in adversarial environments. Pervasive Mob Comput 9(4):546–563 CrossRef Laszka A, Buttyán L, Szeszlér D (2013) Designing robust network topologies for wireless sensor networks in adversarial environments. Pervasive Mob Comput 9(4):546–563 CrossRef
46.
Zurück zum Zitat Alba E, Molina G (2008) Optimal wireless sensor network layout with metaheuristics: solving a large scale instance. In: Lirkov I, Margenov S, Waśniewski J (eds) Large-scale scientific computing. Lecture notes in computer science, vol 4818. Springer, Berlin/Heidelberg, pp 527–535 CrossRef Alba E, Molina G (2008) Optimal wireless sensor network layout with metaheuristics: solving a large scale instance. In: Lirkov I, Margenov S, Waśniewski J (eds) Large-scale scientific computing. Lecture notes in computer science, vol 4818. Springer, Berlin/Heidelberg, pp 527–535 CrossRef
47.
Zurück zum Zitat Deschinkel K (2011) A column generation based heuristic for maximum lifetime coverage in wireless sensor networks. In: SENSORCOMM: the fifth international conference on sensor technologies and applications, Nice, pp 1–6 Deschinkel K (2011) A column generation based heuristic for maximum lifetime coverage in wireless sensor networks. In: SENSORCOMM: the fifth international conference on sensor technologies and applications, Nice, pp 1–6
48.
Zurück zum Zitat Cardei M, Wu J, Lu M, Pervaiz M (2005) Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. In: IEEE international conference on wireless and mobile computing, networking and communications, Montreal, vol 3, pp 438–445 Cardei M, Wu J, Lu M, Pervaiz M (2005) Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. In: IEEE international conference on wireless and mobile computing, networking and communications, Montreal, vol 3, pp 438–445
49.
Zurück zum Zitat Delicato F, Protti F, Pirmez L, de Rezende JF (2006) An efficient heuristic for selecting active nodes in wireless sensor networks. Comput Netw 50(18):3701–3720 CrossRef Delicato F, Protti F, Pirmez L, de Rezende JF (2006) An efficient heuristic for selecting active nodes in wireless sensor networks. Comput Netw 50(18):3701–3720 CrossRef
50.
Zurück zum Zitat Karasabun E, Korpeoglu I, Aykanat C (2013) Active node determination for correlated data gathering in wireless sensor networks. Comput Netw 57(5):1124–1138 CrossRef Karasabun E, Korpeoglu I, Aykanat C (2013) Active node determination for correlated data gathering in wireless sensor networks. Comput Netw 57(5):1124–1138 CrossRef
51.
Zurück zum Zitat Santos AC, Bendali F, Mailfert J, Duhamel C, Hou KM (2009) Heuristics for designing energy-efficient wireless sensor network topologies. J Netw 4(6):436–444 Santos AC, Bendali F, Mailfert J, Duhamel C, Hou KM (2009) Heuristics for designing energy-efficient wireless sensor network topologies. J Netw 4(6):436–444
52.
Zurück zum Zitat Matos VO, Arroyo JEC, dos Santos AG, Goncalves LB (2012) An energy-efficient clustering algorithm for wireless sensor networks. Int J Comput Sci Netw Secu 12(10):6–15 Matos VO, Arroyo JEC, dos Santos AG, Goncalves LB (2012) An energy-efficient clustering algorithm for wireless sensor networks. Int J Comput Sci Netw Secu 12(10):6–15
53.
Zurück zum Zitat Resende MGC, Werneck RF (2004) A hybrid heuristic for the p-median problem. J Heuristics 10:59–88 CrossRef Resende MGC, Werneck RF (2004) A hybrid heuristic for the p-median problem. J Heuristics 10:59–88 CrossRef
54.
Zurück zum Zitat Heinzelman WB, Chandrakasan AP, Balakrishnan H (2000) Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd annual Hawaii international conference on system sciences, Hawaii, vol 2, p 10 Heinzelman WB, Chandrakasan AP, Balakrishnan H (2000) Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd annual Hawaii international conference on system sciences, Hawaii, vol 2, p 10
55.
Zurück zum Zitat Heinzelman WB, Chandrakasan AP, Balakrishnan H (2002) An application-specific protocol architecture for wireless microsensor networks. IEEE Trans Wirel Commun 1: 660–670 CrossRef Heinzelman WB, Chandrakasan AP, Balakrishnan H (2002) An application-specific protocol architecture for wireless microsensor networks. IEEE Trans Wirel Commun 1: 660–670 CrossRef
56.
Zurück zum Zitat Albath J, Thakur M, Madria S (2010) Energy constrained dominating set for clustering in wireless sensor networks. In: 24th IEEE international conference on advanced information networking and applications (AINA), Perth, pp 812–819 Albath J, Thakur M, Madria S (2010) Energy constrained dominating set for clustering in wireless sensor networks. In: 24th IEEE international conference on advanced information networking and applications (AINA), Perth, pp 812–819
57.
Zurück zum Zitat Ferentinos KP, Tsiligiridis TA (2007) Adaptive design optimization of wireless sensor networks using genetic algorithms. Comput Netw 51(4):1031–1051 CrossRef Ferentinos KP, Tsiligiridis TA (2007) Adaptive design optimization of wireless sensor networks using genetic algorithms. Comput Netw 51(4):1031–1051 CrossRef
58.
Zurück zum Zitat Kuila P, Gupta SK, Jana PK (2013) A novel evolutionary approach for load balanced clustering problem for wireless sensor networks. Swarm Evol Comput 12:48–56 CrossRef Kuila P, Gupta SK, Jana PK (2013) A novel evolutionary approach for load balanced clustering problem for wireless sensor networks. Swarm Evol Comput 12:48–56 CrossRef
59.
Zurück zum Zitat Ting C-K, Liao C-C (2010) A memetic algorithm for extending wireless sensor network lifetime. Inform Sci 180(24):4818–4833 CrossRef Ting C-K, Liao C-C (2010) A memetic algorithm for extending wireless sensor network lifetime. Inform Sci 180(24):4818–4833 CrossRef
60.
Zurück zum Zitat Ding L, Gao X, Wu W, Lee W, Zhu X, Du D-Z (2011) An exact algorithm for minimum cds with shortest path constraint in wireless networks. Optim Lett 5(2):297–306 MathSciNetCrossRef Ding L, Gao X, Wu W, Lee W, Zhu X, Du D-Z (2011) An exact algorithm for minimum cds with shortest path constraint in wireless networks. Optim Lett 5(2):297–306 MathSciNetCrossRef
61.
Zurück zum Zitat Gandham S, Dawande M, Prakash R, Venkatesan S (2003) Energy efficient schemes for wireless sensor networks with multiple mobile base stations. In: Proceedings of IEEE globecom 2003, San Francisco, vol 1, pp 377–381 Gandham S, Dawande M, Prakash R, Venkatesan S (2003) Energy efficient schemes for wireless sensor networks with multiple mobile base stations. In: Proceedings of IEEE globecom 2003, San Francisco, vol 1, pp 377–381
62.
Zurück zum Zitat Behdani B, Yun YS, Smith JC, Xia Y (2012) Decomposition algorithms for maximizing the lifetime of wireless sensor networks with mobile sinks. Comput Oper Res 39(5):1054–1061 CrossRef Behdani B, Yun YS, Smith JC, Xia Y (2012) Decomposition algorithms for maximizing the lifetime of wireless sensor networks with mobile sinks. Comput Oper Res 39(5):1054–1061 CrossRef
63.
Zurück zum Zitat Basagni S, Carosi A, Petrioli C, Phillips CA (2009) Heuristics for lifetime maximization in wireless sensor networks with multiple mobile sinks. In: IEEE international conference on communications, ICC’09, Dresden, pp 1–6 Basagni S, Carosi A, Petrioli C, Phillips CA (2009) Heuristics for lifetime maximization in wireless sensor networks with multiple mobile sinks. In: IEEE international conference on communications, ICC’09, Dresden, pp 1–6
64.
Zurück zum Zitat Christofides N (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report 388, Carnegie-Mellon University, Graduate School of Industrial Administration Christofides N (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report 388, Carnegie-Mellon University, Graduate School of Industrial Administration
65.
Zurück zum Zitat Xing G, Wang T, Jia W, Li M (2008) Rendezvous design algorithms for wireless sensor networks with a mobile base station. In: Proceedings of the 9th ACM international symposium on mobile Ad Hoc networking and computing, MobiHoc’08. ACM, New York, pp 231–240 Xing G, Wang T, Jia W, Li M (2008) Rendezvous design algorithms for wireless sensor networks with a mobile base station. In: Proceedings of the 9th ACM international symposium on mobile Ad Hoc networking and computing, MobiHoc’08. ACM, New York, pp 231–240
66.
Zurück zum Zitat Aioffi WM, Valle CA, Mateus GR, da Cunha AS (2011) Balancing message delivery latency and network lifetime through an integrated model for clustering and routing in wireless sensor networks. Comput Netw 55(13):2803–2820 CrossRef Aioffi WM, Valle CA, Mateus GR, da Cunha AS (2011) Balancing message delivery latency and network lifetime through an integrated model for clustering and routing in wireless sensor networks. Comput Netw 55(13):2803–2820 CrossRef
67.
Zurück zum Zitat Üster H, Lin H (2011) Integrated topology control and routing in wireless sensor networks for prolonged network lifetime. Ad Hoc Netw 9(5):835–851 CrossRef Üster H, Lin H (2011) Integrated topology control and routing in wireless sensor networks for prolonged network lifetime. Ad Hoc Netw 9(5):835–851 CrossRef
68.
Zurück zum Zitat Güney E, Aras N, Altinel IK, Ersoy C (2012) Efficient solution techniques for the integrated coverage, sink location and routing problem in wireless sensor networks. Comput Oper Res 39:1530–1539 CrossRef Güney E, Aras N, Altinel IK, Ersoy C (2012) Efficient solution techniques for the integrated coverage, sink location and routing problem in wireless sensor networks. Comput Oper Res 39:1530–1539 CrossRef
69.
Zurück zum Zitat Türkogulları YB, Aras N, Altınel IK, Ersoy C (2010) A column generation based heuristic for sensor placement, activity scheduling and data routing in wireless sensor networks. Eur J Oper Res 207(2):1014–1026 CrossRef Türkogulları YB, Aras N, Altınel IK, Ersoy C (2010) A column generation based heuristic for sensor placement, activity scheduling and data routing in wireless sensor networks. Eur J Oper Res 207(2):1014–1026 CrossRef
70.
Zurück zum Zitat Raiconi A, Gentili M (2011) Exact and metaheuristic approaches to extend lifetime and maintain connectivity in wireless sensors networks. In: Proceedings of the Network optimization: 5th international conference, INOC 2011, Hamburg, 13–16 June 2011. Springer, Berlin/Heidelberg, pp 607–619 Raiconi A, Gentili M (2011) Exact and metaheuristic approaches to extend lifetime and maintain connectivity in wireless sensors networks. In: Proceedings of the Network optimization: 5th international conference, INOC 2011, Hamburg, 13–16 June 2011. Springer, Berlin/Heidelberg, pp 607–619
71.
Zurück zum Zitat Gentili M, Raiconi A (2013) α-coverage to extend network lifetime on wireless sensor networks. Optim Lett 7(1):157–172 MathSciNetCrossRef Gentili M, Raiconi A (2013) α-coverage to extend network lifetime on wireless sensor networks. Optim Lett 7(1):157–172 MathSciNetCrossRef
72.
Zurück zum Zitat Carrabs F, Cerulli R, D’Ambrosio C, Raiconi A (2015) Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints. Technical report, University of Salerno MATH Carrabs F, Cerulli R, D’Ambrosio C, Raiconi A (2015) Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints. Technical report, University of Salerno MATH
73.
Zurück zum Zitat Blum J, Ding M, Thaeler A, Cheng X (2005) Connected dominating set in sensor networks and MANETs. Springer, Boston, pp 329–369 MATH Blum J, Ding M, Thaeler A, Cheng X (2005) Connected dominating set in sensor networks and MANETs. Springer, Boston, pp 329–369 MATH
74.
Zurück zum Zitat Gendron B, Lucena A, da Cunha AS, Simonetti L (2014) Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem. INFORMS J Comput 26(4):645–657 MathSciNetCrossRef Gendron B, Lucena A, da Cunha AS, Simonetti L (2014) Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem. INFORMS J Comput 26(4):645–657 MathSciNetCrossRef
75.
Zurück zum Zitat Buchanan A, Sung JS, Butenko S, Pasiliao (2015) An integer programming approach for fault-tolerant connected dominating sets. INFORMS J Comput 27(1):178–188 Buchanan A, Sung JS, Butenko S, Pasiliao (2015) An integer programming approach for fault-tolerant connected dominating sets. INFORMS J Comput 27(1):178–188
76.
Zurück zum Zitat Türkogulları YB, Aras N, Altınel IK, Ersoy C (2010) An efficient heuristic for placement, scheduling and routing in wireless sensor networks. Ad Hoc Netw 8(6):654–667 CrossRef Türkogulları YB, Aras N, Altınel IK, Ersoy C (2010) An efficient heuristic for placement, scheduling and routing in wireless sensor networks. Ad Hoc Netw 8(6):654–667 CrossRef
77.
Zurück zum Zitat Güney E, Aras N, Altınel IK, Ersoy C (2010) Efficient integer programming formulations for optimum sink location and routing in heterogeneous wireless sensor networks. Comput Netw 54(11):1805–1822 CrossRef Güney E, Aras N, Altınel IK, Ersoy C (2010) Efficient integer programming formulations for optimum sink location and routing in heterogeneous wireless sensor networks. Comput Netw 54(11):1805–1822 CrossRef
78.
Zurück zum Zitat Rajasekaran S, Pardalos P, Hsu DF (2000) Mobile networks and computing. DIMACS – series in discrete mathematics and theoretical computer science, vol 52. American Mathematical Society, Providence Rajasekaran S, Pardalos P, Hsu DF (2000) Mobile networks and computing. DIMACS – series in discrete mathematics and theoretical computer science, vol 52. American Mathematical Society, Providence
79.
Zurück zum Zitat Oliveira CA, Pardalos PM (2011) Mathematical aspects of network routing optimization. Volume 53 of 1931–6828. Springer, New York MATH Oliveira CA, Pardalos PM (2011) Mathematical aspects of network routing optimization. Volume 53 of 1931–6828. Springer, New York MATH
80.
Zurück zum Zitat Resende MG, Pardalos PM (2006) Handbook of optimization in telecommunications. Springer, New York. No. 1 in 78-0-387-30662-9 Resende MG, Pardalos PM (2006) Handbook of optimization in telecommunications. Springer, New York. No. 1 in 78-0-387-30662-9
81.
Zurück zum Zitat Pardalos PM, Ye Y, Boginski VL, Commander CW (2012) Sensors: theory, algorithms, and applications. Volume 61 of 1931–6828. Springer, New York Pardalos PM, Ye Y, Boginski VL, Commander CW (2012) Sensors: theory, algorithms, and applications. Volume 61 of 1931–6828. Springer, New York
82.
Zurück zum Zitat Aioffi WM, Mateus GR, Quintao FP (2007) Optimization issues and algorithms for wireless sensor networks with mobile sink. In: International network optimization conference, Spa Aioffi WM, Mateus GR, Quintao FP (2007) Optimization issues and algorithms for wireless sensor networks with mobile sink. In: International network optimization conference, Spa
83.
Zurück zum Zitat Lin H, Uster H (2014) Exact and heuristic algorithms for data-gathering cluster-based wireless sensor network design problem. IEEE/ACM Trans Netw 22:903–916 CrossRef Lin H, Uster H (2014) Exact and heuristic algorithms for data-gathering cluster-based wireless sensor network design problem. IEEE/ACM Trans Netw 22:903–916 CrossRef
Metadaten
Titel
Optimization Problems, Models, and Heuristics in Wireless Sensor Networks
verfasst von
Vinicius Morais
Fernanda S. H. Souza
Geraldo R. Mateus
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_53

Premium Partner