Properties of RBNs for different values of K. The state cycle length is the median length of the state cycles. B is the network
Technological bounds in digital circuits integration in the last decades have been fostering the development of massively parallel architectures for tasks that had not been touched be- fore by traditional parallel paradigms. Even in personal computers, as well as in consumer and mobile devices, it is common to find powerful processing units composed of processing elements in the range of the hundreds to the thousands.
The request for mobile devices, that are self-powered, almost permanently switched on and connected through wireless networks, as well as environmental friendliness constraints, obviously urges to reduce energy consumption of processing units.
On the other hand, applications continuously keep pushing forward computing power needs. A number of such applications are actually performed on application specific or on almost general-purpose parallel multi-core unit, as in the case of 3D graphics, sound processing, and the like, in the multimedia arena.
The current industrial trend aims to increase computing power and energetic efficiency by adding cores to both main processors and specialized units. A number of experimental architectures have been proposed that try to achieve the same goal by exploiting different designs. Coarse and fine grained architectures, and more in general, reconfigurable architectures have been proposed to make the hardware adapt to the required tasks instead of using specialized software running on general purpose processing elements. This has especially been the case in computer vision, and intelligent systems in general.
More interestingly, in these fields, the quest for massively parallel and energy efficient hardware implementations, coupled with biological models of reference, may pour interest in reviewing well and lesser studied approaches that are centered on self-organizing processing structures. Indeed, current research on pattern recognition shows significant interest in highly structured models built on large numbers of processing nodes trained by demanding algorithms that can, at least partially, be implemented in a parallel fashion.
In this chapter we provide a review of self-organization as it may appears at the various abstract levels of computational architectures, and including applications to real-world problems.
We start outlining the properties related to complexity and self-organization in natural and artificial systems. Then we de-scribe the computational models that are better suited to study self-organizing systems. We then discuss self-organization at the hardware level. Finally, we look at networked systems paying particular attention to distributed sensing networks.
2. Self-organization and self-organizing systems
Human speculation on the visible order of things, either living or not, is so ancient to be considered one of the fundamental questions of mankind. Science has always been exploring the complex structure of Nature, adding pieces to pieces to its infinite puzzle.
Meanwhile, technologies evolve benefiting from new findings, sometimes trying either successfully or ingenuously to duplicate Nature’s work. Improvements in technologies then reflect on further science advancements, closing the loop.
Order, self-organization, adaptation, evolution, emergence and several other terms reminds us that as artificial systems advance, gaining complexity, it is expected for them to be compared to natural ones in both structure and function.
At the time of the vacuum tube digital computer introduction in the 1940s, McCulloch and Pitts had already proposed their neuron model, while cyberneticists were starting to recognize their interdisciplinary studies on natural and artificial systems as a brand new field.
With their simple and primitive circuits, made of few thousands discrete components, digital computers were certainly “complex” with respect to the available technology, but orders of magnitude simpler and unstructured than their biological computational counterparts made of billions of neurons arranged by some “Self-Organization” process.
Anyway, it did not took much to Von Neumann to start exploring the theory of Cellular Automata and self-reproducing machines, attempting to bridge natural and artificial computational models.
Rosenblatt’s perceptron was another attempt to propose a biologically inspired computational framework. As a confirmation of the difficulties in reverse-engineering Nature, it took a few decades for Artificial Neural Networks built with perceptrons to become viable means to tackle useful computational tasks.
Of all the connotations given to perceptron networks, “adaptive” has been certainly one of the most adopted, however many of the terms cited before have found some kind of use with ANNs .
With respect to the “self-organization” term, its use has been used so widespread in computer and information processing literature that the effort to determine its introduction is quite pointless.
One of the most well known uses of the term can be traced back to Kohonen’s “Self-Organizing Maps” (SOMs) . Differently from perceptron based Artificial Neural Networks, trained with supervised algorithms, Kohonen proposed an unsupervised method whose geometrical representation is that of a continuous rearrangement of points of the feature space around auto-determined cluster centers represented as cells in a two-dimensional array. In the topological representation of the evolving map during learning, centers can be visualized as they move forcing the two-dimensional map to stretch in the effort to cover the feature space. Even if SOMs are not a derivation of any biological model, some parallelism with the visual neocortex both in terms of function and structure has been drawn .
Given the impact of SOMs in machine learning and the excitement produced by a simple and effective unsupervised learning algorithm, it is not surprising that a large number of papers followed in Kohonen’s, and that research on SOMs is still carried on actively. Fritzke proposed structures that grow from a small number of cells  modulating the network structure accordingly to the unknown probability distribution of the input.
Other research on SOMs, similarly to the evolution of multi-layered supervised neural networks, introduced some hierarchical organization, as Choi and Park did with their “Self-Creating and Organizing Neural Network” , or Rauber et al. with their “Growing Hierarchical SOM” , or followed the path of hardware implementation of SOMs either in analog , or digital form . A surveillance application was proposed by Chacon-Murguia and Gonzalez-Duarte that mixes SOMs with neuro-fuzzy networks to detect objects in dynamic background for surveillance purposes .
At some point, Dingle and Jones proposed the Chaotic Self Organizing Feature Map  based on recurrent functions leading to chaotic behavior. Continuing this research, more recently Silva et al. proposed a self-organizing recursive architecture for continuous learning . The importance of chaotic dynamics in self-organization will re-emerge in the discussion about computational frameworks.
The relevance of the previously cited work notwithstanding, “self-organization” –in the biological sense– capabilities, should rather be attributed to systems capable of self-assembling from simple elementary units, finding their coordination by direct interactions governed by simple mathematical rules – intrinsic of Nature, it could be stated. Such systems should rather find their biological model in the “prebiotic soup”, in which chemical interactions between atoms and then compounds, lead to the organization of cells, tissues and complex organisms.
Random Boolean Networks (RBNs) were originally introduced by Kauffmann to model gene regulation mechanisms . In Kauffman’s Biology-centered view, evolution is resulting from the Darwinian selection mechanisms coupled with self-organization, adding the concept of “anti-chaos” to the already large and unsettled realm of complex systems.
Cells in biological systems share the same genetic information, nevertheless they differentiate on the basis of specific activation patterns of that very same information. From a computer engineering point of view, this is an upside-down perspective, as changing the software has been the way to make machines adapt to problems.
Indeed, the dichotomy of hardware and software has been the key of early digital computers evolution, permitting to get rid of the hand-wired logic of primordial calculators. Incidentally, if we put apart for a moment most of the involved technological considerations, Von Neumann’s pioneering work on self-reproducing automata was a fifty years forward leap to meet the biological research at some common point.
More or less in the same years as Kauffman, Wolfram meticulously described the complex behavior of one-dimensional cellular automata (Figure 1) pointing out the emergence of self-organization [13, 14].
Coincidentally, at that time the influence of Mandelbrot’s work on fractals was at its peak, as well as the interest for simple formulae able to produce results so similar to those of natural processes . That was certainly a rather inspiring time for those who are subject to the fascination of complexity arising from simplicity but, indeed, this feeling has been pervading the research in information systems for decades.
It was also the time of the advent of networking and – a few more years would have taken the Web to be brought to life – Internet. The latter has the mark of a “self-organizing” system well in its roots, and even in its name, in some way. Then, in a short time lapse, wireless networks broadened the communication horizon once again providing us with mobile systems.
The realm of computers thus has reached a point where interconnected systems at macro scale coexist with the micro scale of the circuits they are built upon, while the nano-dimensionality is being intensively explored. Compared to the many scales adopted to observe biological systems at their molecular, cellular, tissutal and macroscopic levels, this is still a very coarse and rigid stratification, nevertheless provides an interesting parallelism and some points to look at in the distance.
Either in the biological or in the computer realm, more levels bring more complexity. Systems are of different kinds and it needs some “handshaking”, as in the networking jargon, to allow communication. Systems need to share resources, and then some sort of arbitration is needed. A large part of the engineering of information systems has thus become the design of communication and arbitration protocols to make system “self-organize”.
Heylighen and Gershenson invoked self-organization in computers as a necessity to cope with an increasing complexity in information systems that creates a “bottleneck” limiting further progress . They discussed inter-networking, and the rapid changes in hardware, software and protocols to deal with it, as only exacerbating the difficulties for human developers to keep everything under their own control. They then described a few qualitative principles to introduce self-organization in highly engineered and inter-networked information systems, with some references to current applications such as the hyperlinks-based Web, and, with some projections to the future, even software development paradigms.
Kohonen’s networks, the medium access control and routing protocols of the many computer network types, and Kauffman’s RBNs, all of them express self-organization of some degree. The heterogeneity of the three examples is evident, though. Some effort has been taken to formalize this hardly sought property of systems. Gershenson and Heylighen, moving from classical considerations based on thermodynamics, and then considering statistical entropy, provided an insight on what conditions should describe the emergence of self-organization in observed systems.
They concluded that the term “self-organization” may rather describe a way to look at systems than a class of systems .
3. Computational models
As anticipated, Random Boolean Networks (RBNs) trace in their biological model of inspiration their self-organizing abilities. RBNs consist in a network of N nodes with Boolean state, each having K of Boolean input connections. Both parameters N and K are fixed. Because of these characterizing parameters RBNs have also been called NK networks. Each node state is updated at discrete time steps accordingly to a Boolean function of the inputs. A variable number of Boolean outputs, propagating the node state, may departs from each node towards other nodes’ inputs, arbitrarily. Indeed, both connections and the Boolean state update function are chosen randomly during initialization and never changed (Figure 2).
Kauffman discussed RBNs as finite discrete dynamical systems in terms of the sequences of states the networks run through. Given that 2N states can be assumed by RBN, and that for each state there is only one possible successor, the network will run through finite-length cyclic sequences called
The behavior of a RBN can be represented by the state transition diagram, a directed graph having a connected component for each state cycle. Not all the states in each of these sub-graphs are part of the respective cycle, as states having no antecedents – the so-called
Properties of the
When is equal or greater than 5, RBNs keeps showing chaotic behavior. A few concepts need to be introduced to analyze these results. The
In contrast with the first two
|Exponential in N|
The boundaries among the ordered, critical and chaotic dynamical phases, yet not quite analytically assessed, still inspire new studies. An updated introduction to RBNs, including references to Asynchronous RBNs (ARBNs), Deterministic Asynchronous RBNs (DARBNs) and other variants of RBNs, can be found in form of a tutorial in . Gershenson described several methods to guide the self-organization of RBNs . The need of a “guiding” process seems somewhat contradictory with the premise in the title. Indeed, he investigated the mechanisms through which natural selection may intervene in the self-organization of biological structures, suggesting engineers may use the same parameters characterized in computational frameworks, such as RBNs and Cellular Automata.
Getting back to the gene regulation mechanisms the RBNs were designed to model, “self-organization” succeeded in “reducing the complexity” provided by the tens of thousands genes in the human genome to the mere hundreds types of human cells. RBNs are finite state space, deterministic, dynamical, discrete time systems whose self-organizing property derives from having attractors, i.e. states that can be revisited by the network. RBN can be in either a ordered or a chaotic dynamical phase, transitions are possible and the transition from one to the other is “characterized by its criticality”.
A static, stable phase preserves information but is prevented from computing or adapting. A chaotic phase provides the requested variability for computing and adapting, but is incapable of preserving information. As the critical “interface” between the two phases provides the advantages of both phases, guiding the RBN towards self-organizations means finding the necessary conditions to make RBNs evolve towards the critical regime. Gershenson then considered several factors that can induce such evolution and gives a few hints on how criticality could help improve adaptability, ability to evolve, and robustness of RBNs.
4. Cellular automata
From definition it is evident that cellular automata are a special case of RBNs in which each node receives inputs only from neighbors. Their simpler topology and consequent implementation has given an appeal to these minimal models manifesting self-organization that goes beyond “recreational” applications such as Conway’s “Game of Life”.
Some theoretical extensions include Probabilistic Cellular Automata (PCA), and Fault-tolerant Cellular Automata (FCA), studied by Gács  in the context of the problem of reliable computation with unreliable components. In particular, the error probability of each component is not required to decrease as the number of components increases, and the faults affect the local state but not the transition function.
Even if they are purely theoretical, such models may be useful in designing massively parallel “self-organizing” architectures, as due to the distributed nature of information in cellular automata, “self-stabilization” is required beside traditional error-correction techniques.
Cellular automata have had many applications to real-world problems. No surprisingly, several biological models have been simulated with cellular automata. Shumate et al. described a simulation of Ductal Carcinoma in Situ . Chaudary et al. proposed a simulation model for Tumorigenesis . Shimokawa and Muraki investigated a simple model of nerve excitement propagation . Sakamoto et al. proposed a method for surgery simulation based on voxel automata .
Cellular automata have also been used to model complex dynamics such as those of urban traffic [25–27]. Recent applications of cellular automata to image processing include super pixel segmentation , image compression , and computer graphics .
The balance between the hardware and software components in signal processing applications has always been a trade-off between the flexibility of the microprocessor-based solutions and the performance of ASIC implementations.
Taking the aforementioned SOMs and ANNs into account, literature abounds in hardware implementations that are motivated by scarce performance of the analogous sequential methods. In the 1980s, aiming at parallel real-time signal processing with the then available analog very-large-scale integration (VLSI) technology, Chua introduced his Cellular Neural Networks (CNN) , describing some application to image processing tasks . Subsequently, Yang et al. showed a VLSI implementation of CNNs .
A couple of decades later, Ruckert et al. discussed massively parallel implementations of artificial neural networks at ultra-large-scale integration (ULSI) , later showing a massively parallel architecture for SOMs .
Hopfield had started its seminal work on recurrent neural networks posing himself the question whether “the ability of large collection of neurons to perform computational tasks may in part be a spontaneous collective consequence of having a large number of interacting simple neurons”. He concluded that this is actually the case, and that implementation of such models could lead to integrated circuits that are more fault-tolerant than normal circuits .
Weightless Neural Networks (WNNs), being based on random access memories, provide another ANN paradigm inherently tied to circuit-level implementation whose origins trace back to Alexander’s “Self-adaptive universal logic circuits” .
Though all of these are examples of systems having self-adapting qualities, self-organization at the hardware level – the “microscopic” layer in the our biological analogy– had simply not been possible until the advent of reconfigurable circuits, such as field programmable gate arrays (FPGAs), and coarse-grain reconfigurable arrays, added a new degree of configurability, and related complexity, to computer systems. A survey on reconfigurable hardware with emphasis on real-time configuration is provided by Shoa and Shirani .
5.1. Coarse-grained and fine-grained architectures
Hartenstein, reviewing most of the “coarse-grained reconfigurable architectures” of a decade (circa 2000) , suggested that with the explosion of design costs and reduction of production life cycles, performance becomes relatively less important in the design of computing devices. Instead, extension of product longevity, “reduction of support turn-around, in-system debugging, profiling, verification, tuning, field-maintenance, and field-upgrade” time by employing reconfigurable arrays is much more important. Hartenstein, dismissing “von Neumann” architectures as obsolete, in the light of the dominance of host/accelerators designs, proposed a new coarse-grained soft machine paradigm, in which a so called “co-compilation” provides instructions for the host and data-path configuration information at the same time.
Other approaches to the mapping of high-level coarse-grained mapping from high-level synthesis are present in literature . Recently, implementations as System On a Chip design of highly reconfigurable arrays have been described with applications to face detection , Internet protocols processing , FIR filters and ICA . Several SOMs, CNNs and derivative neural network models have been designed for reconfigurable hardware [46, 47].
Fine-grained systems bring configurability close to the gate or transistor level, permitting analog, digital, and hybrid implementations. In contrast to coarse-grained systems, data path width is reduced to the bare minimum, with the advantages of increased flexibility and lower costs, but the general purpose routing is generally less energy efficient.
Nanotechnologies aim at even finer degrees of integration, and it is reasonable to assume that at the hardware level new computational paradigms may emerge because of that. However, as in the pioneering stage of any technology, the span from theory and implementation may not be short. Lin et al. proposed a hybrid FPGA architecture based on nano-RAM  with run-time configuration abilities and high logic density, to revert later to a CMOS SRAM implementation for immaturity of the nano-RAM fabrication processes .
5.2. Evolvable hardware
Reconfigurable hardware is turned into a specific implementation by loading bitstreams compiled from “soft cores” coded in some hardware description language. Being a totally software matter, a host processor can perform real-time reconfiguration when needed. New paradigms blending traditional machine language and reconfigurable hardware bitstreams become thus possible.
The idea that hardware could change autonomously its own configuration seeking the best one according to some fitness function was called evolvable hardware, recurring –once again– to a biological metaphor [50, 51]. Continuing with the metaphor, the bitstream takes the role of the digital DNA (Figure 5).
Approaches from genetic and evolutionary programming are attempted on the hardware configuration bitstream. Interesting applications of EHWs to pattern recognition are those presented by Glette et al. [52, 53].
Even though most work on EHW concerns digital implementations, some evolution-oriented analog implementation are reported in literature, such as the evolvable hardware architecture based on field programmable transistor arrays , and quantum-inspired paradigm to be implemented in evolutionary analog hardware .
The enthusiasm of the early 2000s notwithstanding, EHW has not yet delivered what promised. Cancare et al.  investigating the reasons of this apparently missed success, and citing scalability issues as the most prominent, propose to abandon generic genetic algorithms and look at hierarchical evolution and linkage learning, encouraging support from the Evolutionary Computation community.
Computer networks provide many examples of global behaviors emerging from interactions of elements without centralized control. At different levels of abstraction and implementation, from medium access control and routing, to the application level protocols, algorithms drive each independent network node so that some global goal, be it communication, co- ordination, or distributed processing, is achieved. Thus, non-surprisingly, “self-” prefixed and akin terms abound in related literature.
While computer networks in general are a rather natural field to study self-organization, and many analogies with biological systems may be detected, without broadening too much our discussion, we restrict our discussion considering only one example of network of very simple nodes in which distributed processing of locally collected data is the main goal: Wireless Sensor Networks (WSNs).
These systems are composed by a number of nodes, consisting in miniaturized, battery-operated, computational elements fitted with sensors to monitor the surrounding environment, that are connected through short distance radio links. Depending on the applications, the number of nodes may vary sensibly from a few to thousands and more units. In many scenarios sensor nodes are dispersed in the environment thus their expendability becomes another important requisite.
As a consequence of these constraints on physical size, energy supply and cost per unit, processing resources are limited, and in most designs they only consist in simple microcontrollers. Comprehensive surveys on WSNs including sensor technologies, network protocols, and hardware and software architectures, are provided by Akyldiz et al. , and Yick et al. .
Even though WSNs were conceived as distributed sensing architectures, several examples are provided in literature about nodes also performing in-network pre-processing of raw sensed data . The need for a trade-off between the limited available energy source, and the manifold application scenarios , typically calls for the application of self-organization techniques, breaking the boundaries between the traditional architectural layers in order to optimize the behavior of such nodes. Sohrabi et al. presented a number of algorithms and protocols for self-organization of wireless sensor networks . Self-organization techniques to reduce energy consumption in ad-hoc networks of wireless devices were described by Olascuaga-Cabrera et al. . With even more technological constraints than WSNs, Wireless Sensor Body Networks (WSBNs) consist of wearable and implantable devices. Health-monitoring usage of WSBNs is discussed by Hao and Foster .
Indeed, due to their ultra-low energy consumption requirements, WSBNs represent a very challenging scenario for sensor devices based on current, and even near future, general purpose processing elements, and implementing signal processing algorithms on nodes may prove unfeasible.
Alternative approaches based on application specific integrated circuits have been investigated . Departing from the network oriented vision, and calling for the establishment of self-managing systems engineering, Beal et al. proposed the “amorphous medium” abstraction in which the deployed sensor network represents the physical space of the application to be engineered .
From an engineering perspective, the application goal is reached by programming the medium instead of the network. The former abstracts the computational model, turning sensor nodes into points of the physical space. A global behavior is described in a specifically crafted language, as it were to be executed by the abstract medium. Actually, the abstract description is compiled into code to be executed identically on each node. Besides executing the same code, nodes interact only with neighboring devices.
Beal et al. called this programming paradigm amorphous computing, revealing their inspiration to come from some properties of biological systems, such as morphogenesis and regeneration. More interestingly, even though with substantial topological differences, many similarities can be detected between the “amorphous-medium” and cellular automata.
The paradoxical fascination of simplicity producing complexity has traversed decades of research in information systems. Even more now that extremely high integration is pushing millions of highly modular circuits in few square millimeters, and inter-networking is the next –or rather, current – large scale integration.
Some research directions seem to suggest that breaking some of the fixed ties in engineered system, letting systems auto-organize in response to the environmental changes, as biological systems have been doing for millions of years, is the way to go to “put some order in the chaos”. In support of these indications, self-organizing systems have provided interesting results in modeling complex processes, blurring a little the line between artificial and natural systems.
Other researches seek to extend self-organization to the extreme of self-healing systems able to recognize their own faults and self-repair, while biological applications confirm that taking into account self- organization when studying natural processes, while not an easy task, can provide more comprehensive and effective models.
If all these efforts move on the path towards truly intelligent systems, or even Artificial Life –as some have been suggesting for years– is yet to be discovered, nevertheless it is a very interesting path.