Müller-Schloer / Schmeck / Ungerer Organic Computing — A Paradigm Shift for Complex Systems

1. Auflage 2011
ISBN: 978-3-0348-0130-0
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 627 Seiten

Reihe: Autonomic Systems

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.

Zielgruppe

Research

Autoren/Hrsg.

Müller-Schloer, Christian

Schmeck, Hartmut

Ungerer, Theo

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?;136
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 between 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;347
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 Hormones;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 Signalisation;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: Efficient 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;520
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