Organic Computing has emerged as a challenging vision for future information processing systems. Its basis is the insight that we will increasingly be surrounded by and depend on large collections of autonomous systems, which are equipped with sensors and actuators, aware of their environment, communicating freely, and organising themselves in order to perform actions and services required by the users.
These networks of intelligent systems surrounding us open fascinating ap-plication areas and at the same time bear the problem of their controllability. Hence, we have to construct such systems as robust, safe, flexible, and trustworthy as possible. In particular, a strong orientation towards human needs as opposed to a pure implementation of the tech-nologically possible seems absolutely central. The technical systems, which can achieve these goals will have to exhibit life-like or "organic" properties. "Organic Computing Systems" adapt dynamically to their current environmental conditions. In order to cope with unexpected or undesired events they are self-organising, self-configuring, self-optimising, self-healing, self-protecting, self-explaining, and context-aware, while offering complementary interfaces for higher-level directives with respect to the desired behaviour. First steps towards adaptive and self-organising computer systems are being undertaken. Adaptivity, reconfigurability, emergence of new properties, and self-organisation are hot top-ics in a variety of research groups worldwide.
This book summarises the results of a 6-year priority research program (SPP) of the German Research Foundation (DFG) addressing these fundamental challenges in the design of Organic Computing systems. It presents and discusses the theoretical foundations of Organic Computing, basic methods and tools, learningtechniques used in this context, architectural patterns and many applications. The final outlook shows that in the mean-time Organic Computing ideas have spawned a variety of promising new projects.
Inhaltsverzeichnis
1;Preface;6 1.1; Acknowledgement;8 2;Contents;10 3;Review Team;15 4;Projects;19 5;Contributors;22 6;Chapter 1: Theoretical Foundations;30 6.1;Chapter 1.1: Adaptivity and Self-organisation in Organic Computing Systems;33 6.1.1;1 Introduction;34 6.1.2;2 State of the Art;36 6.1.3;3 Is It Self-organising or Not?;38 6.1.4;4 System Description;40 6.1.5;5 Robustness and Adaptivity;43 6.1.6;6 System Classification;46 6.1.6.1;6.1 Classical Feedback Control Loop System;47 6.1.6.2;6.2 Configuration Space;48 6.1.6.3;6.3 Limitations of Adaptivity;50 6.1.6.4;6.4 Learning;51 6.1.6.5;6.5 Degree of Autonomy;52 6.1.6.6;6.6 Self-organising Systems;54 6.1.7;7 Architectures for Controlled Self-organisation;56 6.1.7.1;7.1 Architectural Options;57 6.1.7.2;7.2 Control Possibilities of OC Systems;58 6.1.7.3;7.3 Roadmap to Ideal OC Systems;59 6.1.8;8 Conclusion;60 6.1.9;9 Outlook;61 6.1.10; References;62 6.2;Chapter 1.2: Quantitative Emergence;66 6.2.1;1 Introduction;66 6.2.2;2 The Measurement of Order;67 6.2.3;3 Observation Model;68 6.2.4;4 Emergence;69 6.2.5;5 Discussion;70 6.2.5.1;5.1 Limitations;70 6.2.5.2;5.2 Redundancy and Emergence;71 6.2.5.3;5.3 Pragmatic Information;72 6.2.6;6 Observer/Controller Architecture;74 6.2.7;7 Experimental Results;75 6.2.7.1;7.1 Experimental Environment;75 6.2.7.2;7.2 Results;75 6.2.7.3;7.3 Prediction;77 6.2.8;8 Conclusion and Outlook;78 6.2.9; References;79 6.3;Chapter 1.3: Divergence Measures as a Generalised Approach to Quantitative Emergence;80 6.3.1;1 Introduction;80 6.3.2;2 State of the Art;81 6.3.3;3 Techniques for Emergence Detection and Measurement;82 6.3.3.1;3.1 Discrete Entropy Difference;82 6.3.3.2;3.2 Divergence-Based Emergence Measures;83 6.3.3.3;3.3 Approximations of Divergence-Based Emergence Measures;84 6.3.4;4 Experimental Results;87 6.3.4.1;4.1 From Chaos To Order;87 6.3.4.2;4.2 Concept Drift;88 6.3.4.3;4.3 Novelty;90 6.3.5;5 Conclusion and Outlook;90 6.3.6; References;92 6.4;Chapter 1.4: Emergent Control;94 6.4.1;1 Introduction;94 6.4.2
;2 Feedback Control and Emergent Control;95 6.4.2.1;2.1 Feedback Control;95 6.4.2.2;2.2 Emergent Control;96 6.4.3;3 Examples;97 6.4.3.1;3.1 EC and FC Result in the Same Macro-behaviour;97 6.4.3.2;3.2 Emergent Control of the Number of Clusters;99 6.4.4;4 How to Construct Macro-to-Micro Feed-Forward Controller?;101 6.4.5;5 Quantitative Comparison of the Performance of Emergent Control vs. Feedback Control;101 6.4.6;6 Discussion, Conclusion, and Outlook;102 6.4.7; References;104 6.5;Chapter 1.5: Constraining Self-organisation Through Corridors of Correct Behaviour: The Restore Invariant Approach;106 6.5.1;1 Introduction;106 6.5.2;2 The Restore Invariant Approach;107 6.5.2.1;2.1 A Formal View on the Restore Invariant Approach;108 6.5.2.2;2.2 Behavioural Guarantees;110 6.5.2.2.1; Verification of the Functional System;110 6.5.2.2.2; Verification of Self-x Mechanisms by Verified Result Checking;111 6.5.3;3 Example Scenario;112 6.5.4;4 Defining Corridors of Correct Behaviour;113 6.5.5;5 Decentralised Restoration of Invariants;114 6.5.5.1;5.1 Coalitions for Local Reconfiguration;114 6.5.5.2;5.2 Coalition Formation Strategy;115 6.5.5.3;5.3 Strategy for Local Variable Violation;116 6.5.5.4;5.4 Strategy for Complete Breakdown of an Agent;117 6.5.5.5;5.5 Discussion;118 6.5.6;6 Summary and Outlook;119 6.5.7; References;119 6.6;Chapter 1.6: Ant Inspired Methods for Organic Computing;121 6.6.1;1 Introduction;121 6.6.2;2 Spatial Organisation of Work and Response-Threshold Models;124 6.6.2.1; Results and Discussion;125 6.6.2.1.1; Effect of Demand Distribution;125 6.6.2.1.2; Demand Redistribution as a Third Task;126 6.6.3;3 Learning from House-Hunting Ants: Collective Decision-Making in Organic Computing Systems;127 6.6.3.1;3.1 Model of the Organic Computing System;128 6.6.3.2;3.2 Results and Discussion;130 6.6.4;4 Sorting Networks of Router Agents;131 6.6.4.1; Results and Discussion;132 6.6.5;5 Summary;133 6.6.6; References;134 6.7;Chapter 1.7: Organic Computing: Metaphor or Model?;1
36 6.7.1;1 Introduction;136 6.7.2;2 Evolutionary Robotics as a Precursor of Organic Computing;137 6.7.3;3 The Evolutionary and the Engineering Paradigm;138 6.7.4;4 Methodological Reconstruction I: Is Evolution Design?;140 6.7.5;5 Methodological Reconstruction II: Is Evolution Optimisation?;143 6.7.6;6 Overcoming Evolutionary Robotics: Organic Computing;145 6.7.7;7 Self-x Properties and the Order of Descriptions;147 6.7.8;8 Conclusion: OC as a New Model-Theoretical Perspective;148 6.7.9; References;149 7;Chapter 2: Methods and Tools;151 7.1;Chapter 2.1: Model-Driven Development of Self-organising Control Applications;154 7.1.1;1 Introduction;154 7.1.2;2 Model-Driven Development;155 7.1.2.1;2.1 Computational Model;157 7.1.2.2;2.2 Model Transformation;158 7.1.3;3 Self-stabilising and Self-organising Algorithm Toolbox;159 7.1.3.1;3.1 Self-stabilising and Self-organising Algorithm Stack;160 7.1.3.2;3.2 Adaptive and Self-optimising Network Algorithms;162 7.1.3.2.1;Adaptive Overlay Topologies;162 7.1.3.2.2;Adaptive Routing;162 7.1.3.3;3.3 Composite Event Detection;164 7.1.4;4 Conclusions;165 7.1.5; References;166 7.2;Chapter 2.2: How to Design and Implement Self-organising Resource-Flow Systems;168 7.2.1;1 Introduction;168 7.2.2;2 Self-organising Resource-Flow Systems;169 7.2.3;3 Software Engineering Guideline;171 7.2.4;4 Functional and Reconfiguration Behaviour;173 7.2.4.1;4.1 An O/C Architecture with Base Agents and Reconfiguration Agents;174 7.2.4.1.1;Base Agent;175 7.2.4.1.2;Reconfiguration Agent;178 7.2.4.2;4.2 Functional Behaviour in Self-organising Resource-Flow Systems;178 7.2.5;5 ODP Runtime Environment;180 7.2.5.1;5.1 Architecture and Behaviour;180 7.2.5.2;5.2 Code Transformation and Extension Points;181 7.2.5.3;5.3 Plug-in Mechanism for Reconfiguration Algorithms;182 7.2.6;6 Conclusion and Future Work;183 7.2.7; References;183 7.3;Chapter 2.3: Monitoring and Self-awareness for Heterogeneous, Adaptive Computing Systems;185 7.3.1;1 Introduction and Motivation;185
7.3.2;2 Related Work;186 7.3.3;3 Monitoring for Heterogeneous, Adaptive Computing Systems;188 7.3.3.1;3.1 Overall Structure;188 7.3.3.2;3.2 Event Coding and Event Space;189 7.3.3.3;3.3 Associative Counter Array;190 7.3.3.4;3.4 High-Level Monitoring;191 7.3.4;4 State Classification and Self-awareness;191 7.3.4.1;4.1 Rule Layout and Online Derivation of Evaluation Rules;191 7.3.4.2;4.2 State Evaluation and Classification;192 7.3.4.3;4.3 Update of Rules at Runtime;193 7.3.5;5 Evaluation and Results;194 7.3.5.1;5.1 Prototypical Hardware Implementation;194 7.3.5.2;5.2 Self-awareness;195 7.3.5.2.1;Initial Classification;195 7.3.5.2.2;Rule-Update at Runtime;196 7.3.6;6 Conclusion and Outlook;197 7.3.7; References;198 7.4;Chapter 2.4: Generic Emergent Computing in Chip Architectures;200 7.4.1;1 Introduction;200 7.4.2;2 Related Work;201 7.4.3;3 Application-Specific Architectures for Marching Pixels Algorithms;202 7.4.3.1;3.1 Implementation of the Flooding Algorithm on FPGAs and ASICs;204 7.4.4;4 The Architecture of ParCA;205 7.4.4.1;4.1 System Overview;205 7.4.4.2;4.2 PE Architecture;207 7.4.4.3;4.3 Types of Double Buffering;210 7.4.4.4;4.4 Simulation Environment;211 7.4.5;5 Results and Layout;211 7.4.6;6 Conclusion and Outlook;212 7.4.7; References;212 7.5;Chapter 2.5: Multi-objective Intrinsic Evolution of Embedded Systems;214 7.5.1;1 Evolvable Hardware-An Introduction;214 7.5.2;2 Models and Algorithms;215 7.5.2.1;2.1 Cartesian Genetic Programs;215 7.5.2.2;2.2 Modular CGP;216 7.5.2.3;2.3 Multi-objective Optimisation Using CGP;217 7.5.2.4;2.4 Challenges of CGP;218 7.5.3;3 Development and Simulation Tools;218 7.5.4;4 Applications;220 7.5.4.1;4.1 Flexible EHW Pattern Matching Architectures;220 7.5.4.2;4.2 Optimising Caches: A High-Performance EHW Application;223 7.5.5;5 Conclusion;225 7.5.6; References;226 7.6;Chapter 2.6: Organisation-Oriented Chemical Programming;228 7.6.1;1 Introduction;228 7.6.2;2 Chemical Reaction Networks, Chemical Organisation Theory, and Movement betw
een Organisations;229 7.6.3;3 Examples;231 7.6.3.1;3.1 A Chemical XOR-Reaction Network, Organisations, and Dynamics;231 7.6.3.2;3.2 Maximal Independent Set Problem-A Chemical Algorithm and a Small Example;233 7.6.3.2.1;General Algorithm;233 7.6.3.2.2;Small Example;235 7.6.4;4 Design Principles;236 7.6.4.1;4.1 Design Principles Derived from Heuristics;236 7.6.4.2;4.2 Design by Evolution;237 7.6.4.3;4.3 Design by Exploration;238 7.6.5;5 Conclusion;239 7.6.6; References;239 7.7;Chapter 2.7: Hovering Data Clouds for Organic Computing;242 7.7.1;1 Introduction;242 7.7.2;2 Related Work;243 7.7.3;3 Concept;244 7.7.4;4 Data Aggregation;246 7.7.4.1;API provided by every sensor:;247 7.7.4.2;API provided by the transport layer:;247 7.7.5;5 Data Dissemination-AutoCast;248 7.7.6;6 Evaluation;250 7.7.6.1;6.1 Data Aggregation;251 7.7.6.2;6.2 AutoCast;252 7.7.7;7 Conclusion and Future Work;254 7.7.8; References;254 8;Chapter 3: Learning;256 8.1;Chapter 3.1: Aspects of Learning in OC Systems;258 8.1.1;1 Introduction;258 8.1.2;2 State of the Art;260 8.1.3;3 Online Learning Using XCS;262 8.1.3.1;3.1 XCS with Rule Combining (XCS-RC);262 8.1.3.2;3.2 Comparison of XCS and XCS-RC;263 8.1.4;4 Optimisation;265 8.1.4.1;4.1 The Role-Based Imitation Algorithm (RBI);265 8.1.4.2;4.2 Optimisation in Dynamic Fitness Landscapes;268 8.1.4.2.1;Parameter Settings and Experimental Results;269 8.1.5;5 Conclusion;270 8.1.6; References;271 8.2;Chapter 3.2: Combining Software and Hardware LCS for Lightweight On-chip Learning;273 8.2.1;1 Introduction;273 8.2.2;2 Related Work;274 8.2.3;3 XCS and LCT;275 8.2.4;4 Methodology;275 8.2.5;5 Experimental Setup;277 8.2.6;6 Results;278 8.2.6.1;6.1 Multiplexer;278 8.2.6.2;6.2 Task Allocation;280 8.2.6.3;6.3 Component Parameterisation;282 8.2.7;7 Conclusions;283 8.2.8; References;284 8.3;Chapter 3.3: Collaborative Learning by Knowledge Exchange;286 8.3.1;1 Introduction;286 8.3.2;2 Overview of Methodological Foundations;287 8.3.2.1;2.1 Layered Architecture of an Organic
Agent;287 8.3.2.2;2.2 Knowledge Representation and Off-line-Training;288 8.3.2.3;2.3 Novelty and Obsoleteness Detection and Reaction;290 8.3.2.4;2.4 Knowledge Extraction and Integration or Fusion;292 8.3.2.5;2.5 Interestingness Assessment;292 8.3.3;3 Experiments;293 8.3.4;4 Conclusion;297 8.3.5; References;298 8.4;Chapter 3.4: A Framework for Controlled Self-optimisation in Modular System Architectures;300 8.4.1;1 Introduction;300 8.4.1.1;1.1 Background;300 8.4.1.2;1.2 Desired Properties of Safe Self-optimisation;301 8.4.2;2 State of the Art;302 8.4.3;3 Framework for Controlled Self-optimisation;304 8.4.3.1;3.1 Overview;304 8.4.3.2;3.2 Directed Self-learning;306 8.4.3.3;3.3 Neuro-fuzzy Elements;308 8.4.3.4;3.4 DSL and the SILKE Approach;308 8.4.3.5;3.5 Self-optimisation and Uncertainties;310 8.4.4;4 Discussion;311 8.4.5;5 Conclusion and Outlook;311 8.4.6; References;312 8.5;Chapter 3.5: Increasing Learning Speed by Imitation in Multi-robot Societies;314 8.5.1;1 Introduction;314 8.5.2;2 Related Work;315 8.5.3;3 ESLAS-An Imitation Supporting Architecture;316 8.5.3.1;3.1 Motivation Layer;316 8.5.3.2;3.2 Strategy Layer;317 8.5.3.3;3.3 Skill Layer;317 8.5.4;4 Enabling Robots to Learn by Imitation;317 8.5.4.1;4.1 Deciding Whom and When to Imitate;318 8.5.4.2;4.2 Interpreting Observed Behaviour;319 8.5.4.3;4.3 Incorporating the Extracted Knowledge;321 8.5.5;5 Results by Simulation;322 8.5.6;6 Conclusion;325 8.5.7; References;326 8.6;Chapter 3.6: Learning to Look at Humans;327 8.6.1;1 Introduction;327 8.6.2;2 Learning Upper Body Models;328 8.6.3;3 Meta-model Construction;330 8.6.4;4 Matching Considerations;331 8.6.5;5 Experimental Results;334 8.6.6;6 Conclusion and Further Work;335 8.6.7; References;338 9;Chapter 4: Architectures;341 9.1;Chapter 4.1: Observation and Control of Organic Systems;343 9.1.1;1 Introduction;343 9.1.2;2 Generic Observer/Controller Architecture;344 9.1.2.1;2.1 System Under Observation and Control;345 9.1.2.2;2.2 Observer;346 9.1.2.3;2.3 Controller;3
47 9.1.3;3 Design Variants of the Observer/Controller Architecture;348 9.1.4;4 Application Survey;349 9.1.4.1;4.1 Central Observer/Controller;350 9.1.4.1.1; Elevator Control;350 9.1.4.1.2; Organic Computing in Off-highway Machines;350 9.1.4.1.3; Cleaning Robots;351 9.1.4.2;4.2 Distributed Observer/Controller Components;351 9.1.4.2.1; Organic Network Control;352 9.1.4.2.2; Organic Traffic Control;352 9.1.4.3;4.3 Multi-levelled Observer/Controller Components;353 9.1.4.3.1; MeRegioMobil;353 9.1.5;5 Conclusion;354 9.1.6; References;354 9.2;Chapter 4.2: Organic Computing Middleware for Ubiquitous Environments;357 9.2.1;1 Introduction;357 9.2.2;2 Related Work;358 9.2.3;3 Initial OC Architecture;359 9.2.3.1;3.1 Middleware Components;360 9.2.3.2;3.2 Messaging;362 9.2.3.3;3.3 Monitoring;362 9.2.3.4;3.4 Self-X Services;363 9.2.3.5;3.5 Shortcomings;364 9.2.4;4 The Refined Architecture;364 9.2.4.1;4.1 Monitor;365 9.2.4.2;4.2 Analyse;365 9.2.4.3;4.3 Plan;366 9.2.4.4;4.4 Execute;367 9.2.5;5 Summary and Outlook;367 9.2.6; References;368 9.3;Chapter 4.3: DodOrg-A Self-adaptive Organic Many-core Architecture;370 9.3.1;1 Introduction;370 9.3.2;2 Organic Hardware;372 9.3.2.1;2.1 Communication Infrastructure;373 9.3.2.2;2.2 Power Management;374 9.3.2.3;2.3 Low-Level Monitoring;375 9.3.2.4;2.4 Hardware Prototype;376 9.3.3;3 Organic Monitoring;376 9.3.4;4 Organic Middleware;378 9.3.5;5 Organic Thermal Management;379 9.3.6;6 Conclusion;382 9.3.7; References;383 9.4;Chapter 4.4: The Artificial Hormone System-An Organic Middleware for Self-organising Real-Time Task Allocation;386 9.4.1;1 Introduction;386 9.4.2;2 The Basic Principle of the Artificial Hormone System;388 9.4.2.1;2.1 Different Kinds of Hormones;389 9.4.2.2;2.2 Constraints of the Artificial Hormone System;391 9.4.3;3 Stability Analysis of the AHS;392 9.4.3.1;3.1 AHS Stability Without Accelerators;392 9.4.3.2;3.2 AHS Stability with Equal Suppressors, Accelerators and Eager Values;393 9.4.3.3;3.3 AHS Stability with Varying Hormone
s;393 9.4.3.4;3.4 AHS Stability with Additional Local Suppressors and Accelerators;393 9.4.4;4 AHS Implementation;394 9.4.5;5 Test Scenario and Results;395 9.4.6;6 Related Work;399 9.4.7;7 Conclusion;400 9.4.8; References;400 9.5;Chapter 4.5: ORCA: An Organic Robot Control Architecture;402 9.5.1;1 Background;402 9.5.2;2 Organic Robot Control Architecture;403 9.5.3;3 Health Signal Principles;406 9.5.3.1;3.1 Health Signals;406 9.5.3.2;3.2 Health Signal Generation;407 9.5.3.3;3.3 Health Signal Fusion;409 9.5.3.4;3.4 Health Signal Processing;410 9.5.4;4 Discussion;412 9.5.5;5 Conclusion and Outlook;413 9.5.6; References;414 9.6;Chapter 4.6: The EPOC Architecture-Enabling Evolution Under Hard Constraints;416 9.6.1;1 Introduction;416 9.6.2;2 Architectural Approach;417 9.6.3;3 Layered Contracting Architecture;417 9.6.4;4 Domain Separation;418 9.6.4.1;4.1 Model Domain;420 9.6.4.2;4.2 Execution Domain;421 9.6.5;5 Observer/Controller Loops;423 9.6.5.1;5.1 Model Domain O/C-Loop;423 9.6.5.1.1;Observer-Model Analysis;423 9.6.5.1.2;Controller-Model Optimisation;424 9.6.5.2;5.2 Execution Domain O/C-Loop;424 9.6.5.2.1;Monitoring Timing Aspects;425 9.6.5.2.2;Monitoring Memory Access Patterns;425 9.6.5.3;5.3 Long-Term Evolution and Quick Reflexes;426 9.6.6;6 Conclusion;427 9.6.7; References;427 9.7;Chapter 4.7: Autonomic System on Chip Platform;430 9.7.1;1 Introduction;430 9.7.2;2 Autonomic SoC Architecture;432 9.7.3;3 Autonomic SoC Architectural Building Blocks;434 9.7.3.1;3.1 Autonomic Processor Core;434 9.7.3.2;3.2 AE Evaluator Architecture;436 9.7.3.3;3.3 Autonomic Element Interconnect;439 9.7.4;4 ASoC Evaluation;440 9.7.5;5 Conclusion;440 9.7.6; References;442 10;Chapter 5: Applications;443 10.1;Chapter 5.1: Organic Traffic Control;446 10.1.1;1 Introduction;446 10.1.2;2 Adaptive Learning Intersections;448 10.1.2.1;2.1 State of the Art;448 10.1.2.2;2.2 An Observer/Controller Architecture for Signal Control;449 10.1.2.2.1; Observing the Traffic;449 10.1.2.2.2; Controlling the Sign
alisation;450 10.1.2.2.3; Experimental Results;451 10.1.3;3 Self-organised Coordination;452 10.1.3.1;3.1 State of the Art;453 10.1.3.2;3.2 Traffic-Responsive Decentralised Coordination;453 10.1.3.2.1; Decentralised Progressive Signal Systems;453 10.1.3.2.2; Experimental Results;454 10.1.3.3;3.3 Limitations of Decentralised Control;455 10.1.3.3.1; Regional Manager;455 10.1.3.3.2; Experimental Results;457 10.1.4;4 Self-organised Routing;457 10.1.4.1;4.1 State of the Art;458 10.1.4.2;4.2 Self-organised Routing;458 10.1.4.2.1; Distance Vector Routing for Road Networks;458 10.1.4.2.2; Experimental Results;459 10.1.5;5 Conclusion;460 10.1.6; References;460 10.2;Chapter 5.2: Methods for Improving the Flow of Traffic;462 10.2.1;1 Introduction;462 10.2.1.1;1.1 Traffic;462 10.2.1.2;1.2 Computing Methodologies in Traffic and Telematics;463 10.2.1.3;1.3 Our Approach;464 10.2.2;2 Traffic Models;465 10.2.2.1;2.1 Single-Lane Traffic;465 10.2.2.2;2.2 Multi-lane Traffic;465 10.2.2.3;2.3 Our Extensions to Krauß's Lane-Change Model;466 10.2.2.4;2.4 Other Models;466 10.2.3;3 Simulation;467 10.2.4;4 Improving the Flow of Highway Traffic;468 10.2.5;5 AutoNomos Strategy Results;469 10.2.5.1;5.1 Single Lane;469 10.2.5.2;5.2 Multiple Lanes;471 10.2.6;6 Urban Traffic;472 10.2.6.1;6.1 Traffic Collapse in an Urban Scenario;472 10.2.6.2;6.2 Flow Over Successive Traffic Lights;473 10.2.6.3;6.3 Rerouting and Recovery;474 10.2.7; References;474 10.3;Chapter 5.3: Applying ASoC to Multi-core Applications for Workload Management;476 10.3.1;1 Introduction;476 10.3.2;2 System Overview;477 10.3.2.1;2.1 Functional Layer;478 10.3.2.2;2.2 Application Software;479 10.3.2.3;2.3 Autonomic Layer;480 10.3.2.3.1;Monitors;480 10.3.2.3.2;Actuators;480 10.3.2.3.3;Evaluator;481 10.3.3;3 Results;482 10.3.3.1;3.1 Comparison of Autonomic and Static Systems;483 10.3.3.2;3.2 Comparison of Autonomic and DVFS Systems;484 10.3.3.3;3.3 Area Overheads;485 10.3.4;4 Conclusion;486 10.3.5; References;486 10.4;Chapter 5.4: Effici
ent Adaptive Communication from Resource-Restricted Transmitters;488 10.4.1;1 Introduction;488 10.4.2;2 A Protocol for Distributed Adaptive Transmit Beamforming in Wireless Sensor Networks;489 10.4.2.1;2.1 Experimental Verification of the Protocol;490 10.4.2.2;2.2 Environmental Impacts on the Performance of the Protocol;491 10.4.2.2.1;Impact of Noise and Interference;492 10.4.2.2.2;Impact of the Network Size;494 10.4.2.3;2.3 Impact of Node Mobility;494 10.4.2.4;2.4 Adaptive Protocols for Distributed Adaptive Beamforming in Wireless Sensor Networks;495 10.4.2.5;2.5 Proposal of Two Adaptive Protocols;495 10.4.2.5.1;An Evolutionary Learning Approach;496 10.4.2.5.2;A Metropolis Learning Approach;497 10.4.3;3 Detection of Environmental Conditions in Wireless Sensor Networks;498 10.4.3.1;3.1 System;498 10.4.3.2;3.2 Features and Classification;498 10.4.3.3;3.3 Experiment;499 10.4.3.3.1;Results;499 10.4.4;4 Conclusion;500 10.4.5; References;501 10.5;Chapter 5.5: OrganicBus: Organic Self-organising Bus-Based Communication Systems;503 10.5.1;1 Introduction;503 10.5.2;2 Model and Problem Definition;504 10.5.2.1;2.1 Types of Streams;506 10.5.2.1.1; Hard Real-Time Streams;506 10.5.2.1.2; Soft Real-Time Streams;506 10.5.2.1.3; Bandwidth Streams;506 10.5.2.2;2.2 Objectives of the Organic Communication System;507 10.5.3;3 Hard Real-Time Streams;507 10.5.4;4 Soft Real-Time Streams;508 10.5.4.1;4.1 DynOAA;509 10.5.4.2;4.2 Results;510 10.5.5;5 Bandwidth Streams;510 10.5.5.1;5.1 Medium Access Game;511 10.5.5.2;5.2 Enhanced Priority-Based Medium Access Game;512 10.5.5.3;5.3 Penalty Learning Algorithm (PLA);512 10.5.5.4;5.4 Results;513 10.5.6;6 Conclusion and Future Work;514 10.5.7; References;515 10.6;Chapter 5.6: OC Principles in Wireless Sensor Networks;516 10.6.1;1 Introduction;516 10.6.2;2 Self-organisation in Wireless Sensor Networks;517 10.6.2.1;2.1 Role Assignment and Adaptive Role Change;517 10.6.2.2;2.2 Clustering Schemes;519 10.6.3;3 Self-healing in Wireless Sensor Networks;52
0 10.6.3.1;3.1 Impaired Node Detection;521 10.6.3.2;3.2 Preventive Role Changing;522 10.6.3.3;3.3 Cluster-Based Rehabilitation;522 10.6.4;4 Robust Scale-Free Routing;525 10.6.5;5 Conclusion and Outlook;528 10.6.6; References;528 10.7;Chapter 5.7: Application of the Organic Robot Control Architecture ORCA to the Six-Legged Walking Robot OSCAR;530 10.7.1;1 Introduction;530 10.7.2;2 Six-Legged Walking Robot OSCAR;531 10.7.3;3 Robot Control Architecture ORCA;532 10.7.4;4 Implementation of ORCA on OSCAR;533 10.7.4.1;4.1 Distributed Leg Control and Self-Organising Gait Patterns;533 10.7.4.2;4.2 Adaptive Walking by Reflexes and Active Compliance;535 10.7.4.3;4.3 Reaction to Anomalies;536 10.7.4.3.1;Weak Anomalies;536 10.7.4.3.2;Medium Anomalies;537 10.7.4.3.3;Strong Anomalies;537 10.7.4.4;4.4 Local Fault Masking by Means of Adaptive Filters;537 10.7.4.5;4.5 Self-reconfiguration in Case of Amputated Legs;538 10.7.4.6;4.6 Primitive Reactive Behaviours;539 10.7.4.7;4.7 Path Planning Based on Health Signals;540 10.7.5;5 Conclusions and Outlook;541 10.7.6; References;542 10.8;Chapter 5.8: Energy-Awareness in Self-organising Robotic Exploration Teams;544 10.8.1;1 Introduction;544 10.8.1.1;1.1 Contents of the Article;545 10.8.1.2;1.2 Related Work;547 10.8.1.3;1.3 Notation;548 10.8.2;2 Energy Spent for Measurements;549 10.8.3;3 Energy Spent for Motion;550 10.8.4;4 Energy Spent for Motion and Measurements;553 10.8.5;5 Conclusion and Outlook;554 10.8.6; References;555 10.9;Chapter 5.9: A Fast Hierarchical Learning Approach for Autonomous Robots;557 10.9.1;1 Introduction;557 10.9.2;2 Overview of the ESLAS Architecture;558 10.9.2.1;2.1 Motivation Layer;559 10.9.2.2;2.2 Strategy Layer;560 10.9.2.3;2.3 Skill Layer;560 10.9.3;3 Ensuring Feasibility by State Abstraction;561 10.9.3.1;3.1 Transition Heuristic;562 10.9.3.2;3.2 Experience Heuristic;562 10.9.3.3;3.3 Failure Heuristic;562 10.9.3.4;3.4 Simplification Heuristic;563 10.9.3.5;3.5 Reward Heuristic;563 10.9.4;4 Learning Skills at the
Lowest Level;564 10.9.5;5 Exploration vs. Exploitation;566 10.9.6;6 Discussion;567 10.9.7;7 Conclusion and Future Work;568 10.9.8; References;569 10.10;Chapter 5.10: Emergent Computing with Marching Pixels for Real-Time Smart Camera Applications;571 10.10.1;1 Introduction;571 10.10.2;2 Related Work;573 10.10.3;3 The Principle of Marching Pixels Algorithms;574 10.10.3.1;3.1 The Basic Procedures of Marching Pixels Algorithms;574 10.10.3.2;3.2 The Local Calculation Tasks of Marching Pixels;575 10.10.3.3;3.3 Example;577 10.10.3.4;3.4 Flooding as an Example of a MP Algorithm;578 10.10.3.5;3.5 Limits of Flooding and Further MP Algorithms;581 10.10.4;4 Outlook and Summary;582 10.10.5; References;583 11;Chapter 6: Status and Outlook;585 11.1;Chapter 6.1.1: OC Techniques Applied to Solve Reliability Problems in Future 1000-Core Processors;586 11.1.1; References;587 11.2;Chapter 6.1.2: Dynamic Classification for Embedded Real-Time Systems;589 11.2.1; References;590 11.3;Chapter 6.1.3: On the Future of Chemistry-Inspired Computing;592 11.3.1; References;593 11.4;Chapter 6.1.4: Agent-Based Thermal Management for Multi-core Architectures;595 11.4.1; References;596 11.5;Chapter 6.1.5: Trust Management-Handling Uncertainties in Embedded Systems;597 11.5.1; References;598 11.6;Chapter 6.1.6: OC-Trust: Towards Trustworthy Organic Computing Systems;600 11.6.1; References;601 11.7;Chapter 6.1.7: Emergence in Action;603 11.7.1;1 Cyber-physical Systems;603 11.7.2;2 Actions;603 11.7.3;3 Run-Time System;604 11.7.4; References;604 11.8;Chapter 6.1.8: Organic Computing in Off-highway Machines;606 11.8.1; References;608 11.9;Chapter 6.1.9: Decentralised Energy Management for Smart Homes;609 11.9.1; References;610 11.10;Chapter 6.1.10: Self-organising Distributed Smart Camera Systems;612 11.10.1; References;613 11.11;Chapter 6.1.11: Organic Network Control;614 11.11.1; References;615 11.12;Chapter 6.2: Organic Computing: Quo vadis?;617 11.12.1;1 Design Time to Runtime;617 11.12.2;2 Cautious
Configuration Space Design;619 11.12.3;3 Self-organisation is not Magic;620 11.12.4;4 Overhead and Complexity;620 11.12.5;5 Runtime Learning (Sandboxing);622 11.12.6;6 OC Devices Can Be Interpreted as Cognitive and Self-optimising Systems;623 11.12.7;7 Definition of Emergence Leads to Analysis of Distribution Functions;623 11.12.8;8 No Decentralisation at Any Cost!;624 11.12.9;9 Human-Centric OC;625 11.12.10;10 Social OC;625 11.12.11;11 Technical Applications?;627 11.12.12;12 Organisational Sciences;627 11.12.13;13 Conclusion;628 11.12.14; References;628