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
Soft Computing
Erschienen in: Soft Computing 12/2013

01.12.2013 | Methodologies and Application

Distributed optimization in wireless sensor networks: an island-model framework

verfasst von: Giovanni Iacca

Erschienen in: Soft Computing | Ausgabe 12/2013

Einloggen

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

search-config
loading …

Abstract

Wireless sensor networks (WSNs) is an emerging technology in several application domains, ranging from urban surveillance to environmental and structural monitoring. Computational intelligence (CI) techniques are particularly suitable for enhancing these systems. However, when embedding CI into wireless sensors, severe hardware limitations must be taken into account. In this paper we investigate the possibility to perform an online, distributed optimization process within a WSN. Such a system might be used, for example, to implement advanced network features like distributed modelling, self-optimizing protocols, and anomaly detection, to name a few. The proposed approach, called DOWSN (distributed optimization for WSN) is an island-model infrastructure in which each node executes a simple, computationally cheap (both in terms of CPU and memory) optimization algorithm, and shares promising solutions with its neighbors. We perform extensive tests of different DOWSN configurations on a benchmark made up of 15 continuous optimization problems; we analyze the influence of the network parameters (number of nodes, inter-node communication period and probability of accepting incoming solutions) on the optimization performance. Finally, we profile energy and memory consumption of DOWSN to show the efficient usage of the limited hardware resources available on the sensor nodes.
Vorheriger Artikel Re-sampled inheritance search: high performance despite the simplicity
Nächster Artikel A greedy gradient-simulated annealing selection hyper-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 "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

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
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The Q16.16 notation indicates that 16 digits are used for the fractional part and 16 for the integer part of the number. The representable range is \([-32768.0,32767.999985],\) with a precision of \(1/65536=0.000015.\) libfixmath provides an overflow detection mechanism which allows developers to check the correctness of operations.
 
2
It should be noted that the packet structure used by the RIME protocol stack imposes an upper bound of 128 bytes for the payload, which in turns limits the maximum amount of information that can be exchanged among nodes. Considering this limit, a maximum number of \(128/4=32\) Q16.16 fixed-point values can be reliably transferred over RIME. Since each packet exchanged in DOWSN contains an n-dimensional array encoding an individual and its fitness (also in Q16.16 format), the upper limit for problem dimension in DOWSN is 31. To overcome this limitation and handle solutions of higher dimensional optimization problems, an application-level protocol should be implemented on top of RIME.
 
3
COOJA is a cross-level simulator for Contiki which allows for simultaneous simulation at network, OS and machine code level. It includes several post-processing plugins, e.g. to estimate the power consumption on each node based on a simple energetic model.
 
4
In a real WSN deployment, these data might be collected on the data flash memory on the motes and then analyzed for post-processing. Another option would be a “sink” node connected to a PC: in this scenario, the sink would listen periodically to broadcast packets in order to provide the user, in real-time, the global output.
 
5
Recalling that the standard error of the mean of a n-dimensional sample whose variance is \(\sigma \) is \(\sigma /\!\sqrt{n},\) and applying the central limit theorem to approximate the sample mean with a normal distribution, it follows that a sample size \(n=16\sigma ^2/ W^2\) guarantees a 95 % confidence interval of width \(W.\)
 
Literatur
Abdul Latiff NM, Tsimenidis CC, Sharif BS, Ladha C (2008) Dynamic clustering using binary multi-objective particle swarm optimization for wireless sensor networks. Comput Eng 2(2):1–5
Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E (2002) Wireless sensor networks: a survey. Comput Netw 38:393–422CrossRef
Attea BA, Khalil EA (2012) A new evolutionary based routing protocol for clustered heterogeneous wireless sensor networks. Appl Soft Comput 12(7):1950–1957CrossRef
Bass F (1969) A new product growth model for consumer durables. Manag Sci 15:215–227CrossRefMATH
Brooks SH (1958) A discussion of random methods for seeking maxima. Oper Res 6(2):244–251CrossRef
Canada-Bago J, Fernandez-Prieto JA, Gadeo-Martos MA, Velasco JR (2010) A new collaborative knowledge-based approach for wireless sensor networks. Sensors 10(6):6044–6062CrossRef
Caputo D, Grimaccia F, Mussetta M, Zich RE (2010) Genetical swarm optimization of multihop routes in wireless sensor networks. Appl Comput Intell Soft Comput 2010:14
Curren D (2008) A survey of simulation in sensor networks. Architecture 7:867–872
Deshpande A, Guestrin C, Madden S, Hellerstein JM, Hong W (2004) Model-driven data acquisition in sensor networks. In: VLDB, pp 588–599
Föerster A, Murphy AL (2010) Machine learning across the WSN layers, InTechWeb Publishing, pp 165–182
García-Hernández CF, Ibargüengoytia-González PH, García-Hernández J, Pérez-Díaz JA (2007) Wireless sensor networks and applications: a survey. J Comput Sci 7(3):264–273
Guestrin C, Bodík P, Thibaux R, Paskin MA, Madden S (2004) Distributed regression: an efficient framework for modeling sensor network data. In: IPSN, pp 1–10
Guo H, Low KS, Nguyen HA (2011) Optimizing the localization of a wireless sensor network in real time based on a low-cost microcontroller. IEEE Trans Indust Electr 58(3):741–749CrossRef
Guo L, Li Q, Chen F (2011) A novel cluster-head selection algorithm based on hybrid genetic optimization for wireless sensor networks. JNW 6(5):815–822CrossRef
Harrop P, Das R (2012) Wireless sensor networks 2012–2022: the new market for ubiquitous sensor networks (USN). IDTechEx
Hedar AR, Fukushima M (2003) Heuristic pattern search and its hybridization with simulated annealing for nonlinear global optimization. Kyoto University, Kyoto
Hooke R, Jeeves TA (1961) Direct search solution of numerical and statistical problems. J ACM 8:212–229CrossRefMATH
Iacca G (2012) Introducing DOWSN: distributed optimization in wireless sensor networks. In: Computational intelligence (UKCI), 2012 12th UK Workshop on, pp 1–8
Iacca G, Neri F, Mininno E, Ong YS, Lim MH (2012) Ockham’s Razor in memetic computing: three stage optimal memetic exploration. Inform Sci 188:17–43MathSciNetCrossRef
Johnson DM, Teredesai A, Saltarelli RT (2005) Genetic Programming in Wireless Sensor Networks. In: EuroGP, pp 96–107
Kulkarni RV, Forster A, Venayagamoorthy GK (2011) Computational intelligence in wireless sensor networks: a survey. IEEE Commun Surv Tutor 13(1):68–96CrossRef
Kulkarni RV, Venayagamoorthy GK (2011) Particle swarm optimization in wireless-sensor networks: a brief survey. IEEE Trans Syst Man Cybern Part C 41(2):262–267CrossRef
Kulkarni RV, Venayagamoorthy GK, Cheng MX (2009) Bio-inspired node localization in wireless sensor networks. In: Proceedings of the 2009 IEEE international conference on systems, man and cybernetics, SMC’09, IEEE Press, pp 205–210
Low KS, Nguyen HA, Guo H (2008) A particle swarm optimization approach for the localization of a wireless sensor network. In: 2008 IEEE international symposium on industrial electronics, pp 1820–1825
Michalewicz Z (1996) Genetic algorithms + Data structures = Evolution programs. Springer-Verlag, LondonCrossRefMATH
Mihaylov M, Tuyls K, Nowé A (2010) Decentralized learning in wireless sensor networks. Lect Note Comput Sci(Springer Berlin/Heidelberg) 5924:60–73CrossRef
Nabi M, Blagojevic M, Basten T, Geilen M, Hendriks T (2009) Configuring multi-objective evolutionary algorithms for design-space exploration of wireless sensor networks. In: Proceedings of the 4th ACM workshop on performance monitoring and measurement of heterogeneous wireless and wired networks, PM2HW2N ’09. ACM, New York, pp 111–119
Nan G, Li M (2008) Evolutionary based approaches in wireless sensor networks: a survey. In: Proceedings of the 2008 fourth international conference on natural computation, vol 05, ICNC ’08. IEEE Computer Society, pp 217–222
Neri F, Iacca G, Mininno E (2011) Disturbed exploitation compact differential evolution for limited memory optimization problems. Inform Sci 181(12):2469–2487MathSciNetCrossRef
Nguyen X, Jordan MI, Sinopoli B (2005) A kernel-based learning approach to ad hoc sensor network localization. TOSN 1(1):134–152CrossRef
Okdem S, Karaboga D (2009) Routing in wireless sensor networks using an ant colony optimization (ACO) router chip. Sensors 9(2):909–921CrossRef
Österlind F, Dunkels A, Eriksson J, Finne N, Voigt T (2006) Cross-level sensor network simulation with COOJA. In: Proceedings of the first IEEE international workshop on practical issues in building sensor network applications (SenseApp ’06), Florida
Paskin MA, Guestrin C (2004) Robust probabilistic inference in distributed systems. In: UAI, pp 436–445
Paskin MA, Guestrin C, McFadden J (2005) A robust architecture for distributed inference in sensor networks. In: IPSN, pp 55–62
Polastre J, Szewczyk R, Culler D (2005) Telos: enabling ultra-low power wireless research. In: Proceedings of the 4th international symposium on information processing in sensor networks, IPSN ’05. IEEE Press, Piscataway
Predd JB, Kulkarni SR, Poor HV (2005) Distributed regression in sensor networks: training distributively with alternating projections. In Proceedings of the SPIE conference and advanced signal processing algorithms, architectures, and implementations XV (invited), San Deigo.
Predd JB, Kulkarni SR, Poor HV (2006) Distributed learning in wireless sensor networks. IEEE Signal Process Mag 23(4):56–69. ISSN 1053–5888
Qin AK, Huang VL, Suganthan PN (2009) Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans Evol Comput 13(2):398–417CrossRef
Rabbat M, Nowak R (2004) Distributed optimization in sensor networks. In: Proceedings of the 3rd international symposium on information processing in sensor networks, IPSN ’04. ACM, New York, pp 20–27
Rabbat M, Nowak R (2005) Quantized incremental algorithms for distributed optimization. Select Area Commun IEEE J 23(4):798–808CrossRef
Reddy AMV, Kumar AVUP, Janakiram D, Kumar GA (2009) Wireless sensor network operating systems: a survey. Int J Sen Netw 5(4):236–255CrossRef
Suganthan PN, Hansen N, Liang JJ, Deb K, Chen YP, Auger A, Tiwari S (2005) Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. In: Technical report 2005005, Nanyang Technological University and KanGAL, Singapore
Tam V, Cheng KY, Lui KS (2006) Using micro-genetic algorithms to improve localization in wireless sensor networks. J Commun 1(4):137–141
Tanese R (1987) Parallel genetic algorithms for a hypercube. In: Proceedings of the second international conference on genetic algorithms on genetic algorithms and their application. L. Erlbaum Associates Inc., Hillsdale, pp 177–183
Tanese R (1989) Distributed genetic algorithms. In: Proceedings of the 3rd international conference on genetic algorithms. Morgan Kaufmann Publishers Inc., San Francisco, pp 434–439
Terwilliger M, Gupta AK, Khokhar AA, Greenwood GW (2005) Localization using evolution strategies in sensornets. In: Congress on evolutionary computation,IEEE, pp 322–327
Tseng LY, Chen C (2008) Multiple trajectory search for large scale global optimization. In: Proceedings of the IEEE congress on, evolutionary computation, pp 3052–3059
Valencia P, Lindsay P, Jurdak R (2010) Distributed genetic evolution in WSN. ACM Press, p 13
Vesterstrøm J, Thomsen R (2004) A comparative study of differential evolution, particle swarm optimization and evolutionary algorithms on numerical benchmark problems. In: Proceedings of the IEEE congress on evolutionary computation, vol 3, pp 1980–1987
Wang X, Ma JJ, Wang S, Bi DW (2007) Distributed particle swarm optimization and simulated annealing for energy-efficient coverage in wireless sensor networks. Sensors 7(5):628–648CrossRef
Weise T, Geihs K (2006) Genetic programming techniques for sensor networks. In: Marrón PJ (ed) Proceedings of 5. GI/ITG KuVS fachgesprach drahtlose sensornetze, Technical, Report No. 2006/07, vol. 2006/07. University of Stuttgart, Stuttgart, pp 21–25
Whitley D, Rana S, Heckendorn RB (1998) The island model genetic algorithm: on separability, population size and convergence. J Comput Inform Technol 7:33–47
Wilcoxon F (1945) Individual comparisons by ranking methods. Biomet Bull 1(6):80–83CrossRef
Xinchao Z (2011) Simulated annealing algorithm with adaptive neighborhood. Appl Soft Comput 11(2):1827–1836CrossRef
Yang S, Huang R, Shi H (2006) Mobile agent routing based on a two-stage optimization model and a hybrid evolutionary algorithm in wireless sensor networks. In: Jiao L, Wang L, Gao X, Liu J, Wu F (eds) Advances in natural computation, lecture notes in computer science, vol 4222. Springer, Berlin, pp 938–947
Yap DFW, Koh SP, Tiong S (2011) Mathematical function optimization using AIS antibody remainder method. Intern J Mach Learn Comput 1(1):13–19CrossRef
Yick J, Mukherjee B, Ghosal D (2008) Wireless sensor network survey. Comput Netw 52(12):2292–2330CrossRef
Zaharie D (2002) Parameter adaptation in differential evolution by controlling the population diversity. In: Petcu D et al (eds) Proceedings of the international workshop on symbolic and numeric algorithms for scientific, computing, pp 385–397
Zaharie D (2003) Control of population diversity and adaptation in differential evolution algorithms. In: Matousek D, Osmera P (eds) Proceedings of MENDEL international conference on, soft computing, pp 41–46
Zhou J, Ji Z, Shen L (2008) Simplified intelligence single particle optimization based neural network for digit recognition. In: Proceedings of the Chinese conference on, pattern recognition, pp 1–5 (10311847)
Metadaten
Titel
Distributed optimization in wireless sensor networks: an island-model framework
verfasst von
Giovanni Iacca
Publikationsdatum
01.12.2013
Verlag
Springer Berlin Heidelberg
Erschienen in
Soft Computing / Ausgabe 12/2013
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-013-1091-x

Weitere Artikel der Ausgabe 12/2013

Soft Computing 12/2013 Zur Ausgabe

Methodologies and Application

Intelligent synthetic composite indicators with application

Methodologies and Application

Swarm intelligence and the quest to solve a garbage and recycling collection problem

Methodologies and Application

A genetic type-2 fuzzy logic based system for the generation of summarised linguistic predictive models for financial applications

Editorial

Advances in computational intelligence (UKCI 2012)

Methodologies and Application

Comparison of algorithms that detect drug side effects using electronic healthcare databases

Methodologies and Application

A prediction-based adaptive grouping differential evolution algorithm for constrained numerical optimization

Premium Partner

    Bildnachweise