Don't re-invent the wheel: go for bio!

Bio-inspired Networking – Challenges and Opportunities

By Dr. Falko Dressler, Univ. of Erlangen

New achievements in electronics and the increasing demand for novel communication services fostered the development of network technologies that are envisioned to support future communication needs. Significant research especially focused on wireless networks that are representing one of the most challenging domains in computer networking. In order to support the needs of future applications and to generate a completely new generation of wireless networking architectures, a number of challenges need to be addressed: scalability issues in terms of the number of supported network nodes and the amount of exchanged data; inherent dynamics of the system w.r.t. environmental conditions and the possibly frequent addition/removal of nodes; resource constraints – primarily the available energy of mobile devices; support for heterogeneous hardware and software; and the lack of a fixed network infrastructure that has been used for management and control of the entire network [Akyildiz2004, Chlamtac2003]. Self-organization is envisioned to be the basis for such a new era of autonomic communication networks [Dressler2007].

The turn to nature for solutions to technological questions has brought us many unforeseen great concepts. This encouraging course seems to hold on for many aspects in technology. First approaches to classify bio-inspired solutions and to explicitly exploit concepts and ideas for the development of novel improved systems, and to encourage further research in this domain, date back to the 1970ies [Eigen1979]. Numerous algorithms and techniques have been proposed which are based on bio-inspired research. The most prominent domains used in computer science have been evolutionary techniques such as genetic algorithms [Goldberg1989]. Both represent a class of optimization algorithms used in domains in which a full search is either inappropriate due to time or resource limitations of not feasible at all.

In the late 1990ies, a new domain of this bio-inspired systems research has been initiated, which is usually known as bio-inspired networking. It turned out that a number of solutions studied in biology have similar counterparts in the networking domain. Especially when looking at massively distributed systems such as wireless sensor networks or wireless mesh networks, the efficiency and simplicity of biological systems is providing solutions as fascinating as efficient. Whereas some of the first publications in this field have been full of metaphors without much impact on the networking technology, meanwhile, a visible number of highly successful approaches have been proposed for a wide range of applications. In the following, some specific approaches are listed that have been selected for two reasons: first, the approach has been carefully modeled and the technical solutions mimicking the biological behavior clearly outperform related engineering approaches.

• Ant colony optimization (ACO) – Ants are able to solve complex tasks by simple local means. There is only indirect interaction between individuals through modifications of the environment, e.g. pheromone trails are used for efficient foraging. Ants are “grand masters” in search and exploration. [Bonabeau1999]. Application in networking includes routing in ad hoc networks and overlays as well as task allocation mechanisms [Di Caro1998].

• Firefly synchronization – Precise synchronization in massively distributed systems is a complex issue and hard to achieve. Recently, new models for clock synchronization have been proposed based on the synchronization principles of fireflies that is based on pulse-coupled oscillators [Mirollo1990]. This concept of self-organized clock synchronization has been successfully applied to synchronization in ad hoc networks [Tyrrell2006].

• Artificial immune system (AIS) – The primary goal of an AIS, which is inspired by the principles and processes of the mammalian immune system [Hofmeyr2000], is to efficiently detect changes in the environment or deviations from the normal system behavior in complex problems domains. A typical approach is therefore the misbehavior detection in communication networks, e.g. in ad hoc networks [Le Boudec2004].

• Epidemic communication – Epidemic spreading is frequently used as an analogy to understand information dissemination in ad hoc networks. Information dissemination in this context usually refers to the distribution of information particles. A deep understanding of topology models, i.e. models reflecting strong spatial effects with nodes at fixed positions in two dimensions vs. scale-free networks, helps to develop ad hoc routing techniques that outperform classical approaches [Carreras2006, Vogels2003].

• Cellular signaling networks – Signaling in biological systems occurs at multiple levels and in many shapes [Weng1999] – such communication structures are also known as signaling pathways. A key challenge for biology is to understand the structure and the dynamics of the complex web of interactions that contribute to the structure and function of a living cell. Using similar approaches to programming autonomous network systems lead to the development of programming paradigms like Fraglets [Tschudin2003] and RSN [Dressler2009], both providing support for light-weight control of distributed actions according to specific characteristics of received messages.

All the listed approaches to bio-inspired networking show common aspects such as their inherent support for adaptive operation, the robustness against changing environmental conditions, self-organization capabilities, and optimized scalability. On the other hand, the addressed application scenarios are as different as their biological counterparts. In conclusion, it can be said that the domain of bio-inspired networking is an emerging area that already yielded to solutions with great and astonishing characteristics. The most challenging issue in this field is the careful selection of the appropriate biological counterpart, a thorough modeling of both the technical and the biological system, and finally a comprehensive comparison to classical engineering solutions.

References:

[Akyildiz2004] I. F. Akyildiz and I. H. Kasimoglu, "Wireless Sensor and Actor Networks: Research Challenges," Elsevier Ad Hoc Networks, vol. 2, October 2004, pp. 351-367.

[Bonabeau1999] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York, 1999.

[Carreras2006] I. Carreras, D. Miorandi, G. S. Canright, and K. Engo-Monsen, "Understanding the Spread of Epidemics in Highly Mobile Networks," Proceedings of 1st IEEE/ACM International Conference on Bio-Inspired Models of Network, Information and Computing Systems (IEEE/ACM BIONETICS 2006), Cavalese, Italy, December 2006.

[Chlamtac2003] I. Chlamtac, M. Conti, and J. J. Liu, "Mobile ad hoc networking: imperatives and challenges," Elsevier Ad Hoc Networks, vol. 1 (1), July 2003, pp. 13-64.

[Di Caro1998] G. Di Caro and M. Dorigo, "AntNet: Distributed Stigmergetic Control for Communication Networks," Journal of Artificial Intelligence Research, vol. 9, December 1998, pp. 317-365.

[Dressler2007] F. Dressler, Self-Organization in Sensor and Actor Networks. John Wiley & Sons, Chichester, 2007.

[Dressler2009] F. Dressler, I. Dietrich, R. German, and B. Krüger, "A Rule-based System for Programming Self-Organized Sensor and Actor Networks," Elsevier Computer Networks, 2009. (to appear)

[Eigen1979] M. Eigen and P. Schuster, The Hypercycle: A Principle of Natural Self Organization. Springer, Berlin, 1979.

[Goldberg1989] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Kluwer Academic Publishers, Boston, 1989.

[Hofmeyr2000] S. A. Hofmeyr and S. Forrest, "Architecture for an Artificial Immune System," Evolutionary Computation, vol. 8 (4), 2000, pp. 443-473.

[Le Boudec2004] J.-Y. Le Boudec and S. Sarafijanovic, "An Artificial Immune System Approach to Misbehavior Detection in Mobile Ad-Hoc Networks," Proceedings of 1st International Workshop on Biologically Inspired Approaches to Advanced Information Technology (Bio-ADIT2004), Lausanne, Switzerland, January 2004, pp. 96-111.

[Mirollo1990] R. E. Mirollo and S. H. Strogatz, "Synchronization of Pulse-Coupled Biological Oscillators," SIAM Journal on Applied Mathematics, vol. 50 (6), December 1990, pp. 1645-1662.

[Tschudin2003] C. Tschudin, "Fraglets - a Metabolistic Execution Model for Communication Protocols," Proceedings of 2nd Symposium on Autonomous Intelligent Networks and Systems (AINS), Menlo Park, CA, June/July 2003.

[Tyrrell2006] A. Tyrrell, G. Auer, and C. Bettstetter, "Fireflies as Role Models for Sychronization in Ad Hoc Networks," Proceedings of 1st IEEE/ACM International Conference on Bio-Inspired Models of Network, Information and Computing Systems (IEEE/ACM BIONETICS 2006), Cavalese, Italy, December 2006.

[Vogels2003] W. Vogels, R. van Renesse, and K. Briman, "The Power of Epidemics: Robust Communication for Large-Scale Distributed Systems," ACM SIGCOMM Computer Communication Review, vol. 33 (1), January 2003, pp. 131-135.

[Weng1999] G. Weng, U. S. Bhalla, and R. Iyengar, "Complexity in Biological Signaling Systems," Science, vol. 284 (5411), April 1999, pp. 92-96.