第4卷第4期 智能系统学报 Vol.4 No.4 2009年8月 CAAI Transactions on Intelligent Systems Ag.2009 doi:10.3969/j.issn.16734785.2009.04.015 Biologically inspired self-organizing networks Naoki WAKAMIYA,Kenji LEIBNITZ,Masayuki MURATA Graduate School of Information Science and Technology,Osaka University,Osaka 565-0871,Japan) Abstract:Information networks are becoming more and more complex to accommodate a continuously increasing amount of traffic and networked devices,as well as having to cope with a growing diversity of operating environments and applications.Therefore, it is foreseeable that future information networks will frequently face unexpected problems,some of which could lead to the com- plete collapse of a network.To tackle this problem,recent attempts have been made to design novel network architectures which achieve a high level of scalability,adaptability,and robustness by taking inspiration from self-organizing biological systems.The objective of this paper is to discuss biologically inspired networking technologies. Keywords:self-organization;biological systems;adaptability;robustness;swarm intelligence;attractor selection CLC Number:TP18 Document code:A Doument ID:1673-4785(2009)04-0369-07 In our everyday life we are surrounded by a huge based on an estimation or prediction of the number of number of information processing devices,such as per- users and their behavior,the amount of traffic they will sonal computers,mobile phones,video game consoles, produce,and the expected operational environment. television sets,digital video recorders,automatic teller Furthermore,in order to improve their robustness,net- machines,and vending machines,which are directly works are equipped with failure recovery mechanisms or indirectly connected to networks and provide us with based on predictions of the type,magnitude,and dura- a variety of networked information services.With the tion of possibly occurring failures,and they are de- advancement of mobile phone technology and the pro- ployed with additional tolerance margins to treat further liferation of new devices,such as RFID (radio fre- exceptional cases.Therefore,such conventional net- quency identification )new networked information works can operate in a desired way as long as the oper- services are expected to emerge in the very near future ational conditions are within the expected range.Un- and more diverse types of information will be ex- fortunately,they are vulnerable and may easily col- changed between these devices. lapse once an unexpected amount of traffic or unexpect- 1 Introduction ed demand is encountered,either due to abuse,at- tacks,or unexpected failures for which the network was To accommodate such large numbers of heteroge- simply not prepared.Furthermore,due to the enor- neous types of devices and the tremendous amount of mous complexity of such networks,it may take a sub- traffic they generate,information networks are becom- stantial amount of time to recover from such failures. ing more complex and sophisticated.Following design Taking into account the diversity and unpredict- methodologies for conventional network architectures, ability of the operational environment,future informa- networks are usually optimized for best performance tion networks need to be capable of maintaining a high Received Data:2009-01-12. level of scalability,adaptability,and robustness.Re- Contact Author:Kenji leibnitz.E-mail:leibnitz@ist.osaka-u.ac.jp. cently,the field of biologically inspired networking has
.370. 智能系统学报 第4卷 been attracting many researchers and developers,since Such unused resources are the source of adaptability it appears highly promising as a means to establish and robustness,and similar strategies of tradeoffs be- more scalable,adaptive,and robust information net- tween quantity and quality will also be essential for fu- works.The source of the emergence of scalability,a- ture network technologies. daptability,and robustness in biological systems is Performance conventional network their inherently self-organizing structure.Global and bio-inspired self organizing collective behavior of a self-organizing system is network reached through local interactions among the entities constituting the system.Each entity operates on a set of simple rules and behaves in accordance with entirely number and scale of failures,degree of changes... local information that can be obtained through observa- tion of its local surroundings and communication with Fig.1 Comparison of self-organizing networks and conven- its neighbors.Bonabeau etastate four principles of tional networks.Self-organizing networks should be self-organization.These principles are:positive feed- inferior in performance to conventional networks un- back to reinforce good control;negative feedback to der ideal conditions,but show greater resilience un- suppress overshooting and provide stabilization;direct der unexpected conditions. and/or indirect interactions among entities;exploita- Although it is also possible for a conventional sys- tion of fluctuations to leap from local suboptimal solu- tem to improve its adaptability and robustness by intro- tions. ducing additional and redundant network resources and A self-organizing system does not have a central- more sophisticated recovery mechanisms,this would ized control unit dominating the whole system;emer- only result in a slight shifting of the critical point to the gence of controllers lies in the nature of self-organiza- right in Fig.1,remaining far below the range of adapt- tion.Owing to this fact,a self-organizing system has ability and tolerance that a self-organizing system pos- high adaptability and robustness;however,this is at the sesses. cost of performance.When the operational conditions 2 Lessons from biological dynamics stay within the expected range,a conventional and opti- mally designed system on a centralized architecture a- Biological systems are highly dynamical systems. chieves better performance and is superior to a self-or- They control,regulate,and adapt themselves accord- ganizing system as intuitively illustrated in Fig.1. ing to observations of their dynamically changing sur- However,we argue that this lower performance roundings,their internal condition,and their interac- will eventually be compensated for by advancements in tion with neighboring organisms,e.g.,individuals or network technologies,such as increases in channel ca- cells. pacity and the development of new devices.Instead, 2.1 Self-organizing network control inspired by we would do better directing our attention to the adapt- swarm intelligence ability and robustness of self-organizing systems rather Swarm intelligence is organized collective behavior than to their performance.In fact,self-organizing bio- emerging from local interactions among simple agents in logical systems are not structured to achieve optimal a colony of social insects such as ants or bees performance since they must continue to slowly evolve One of the well-known examples of swarm intelli- while adapting to a dynamically changing environment. gence is the foraging behavior of ants,which find the There are always some spare or even idle resources and shortest path from their nest to a food source through sometimes even inefficient control can be observed
第4期 Naoki WAKAMIYA,et al:Biologically inspired self-organizing networks .371. indirect interaction among each other mediated by In the case of swarms of bees,they efficiently pheromone trails (see Fig.2).The underlying theo- share roles within their colony,such as foraging and retic model,called ant colony optimization (ACO)2, nesting,based on needs without any centralized con- is known as a heuristic for the travelling salesman prob- trol.In the response threshold model,each individual lem (TSP)and has been successfully applied in rou- has a threshold which expresses their willingness or ting protocols,for example,AntNet[31 hesitation to perform a given task.When demand for food phase pheromone stimuli a task exceeds this threshold,there is a high probabili- d9=1+A)△) ty an individual will become engaged in the task.In addition,there is a reinforcement mechanism which phase-response curve generates specialists for a certain task7.Once an in- dividual has performed a task for a period of time,it nest establishment of shortest path pulse-coupled oscillator model lowers its threshold for that task and becomes more by pheromones and flashing freflies likely to perform the task in the future.This method of Fig.2 Examples of swarm intelligence:foraging ants and division of labor gives the colony high resilience.When synchronously flashing fireflies individuals performing a certain task are eliminated, others dedicated to another task eventually begin taking Another similar example shown in Fig.2 can be over this task and as a result the appropriate balance of found in the interactions of groups of fireflies or crick- role sharing is maintained.As an example,we can ets(41.Some species of fireflies exhibit synchronized consider the task of caching in a content sharing net- behavior in flashing.A firefly periodically flashes ac- work.The amount of cached content in the network cording to its intrinsic timer when it is not interacting can be balanced,eventually resulting in excessively re- with other fireflies.However,when fireflies form a dundant content being discarded and a smaller cache group,a flash of one firefly stimulates others in its vic- being maintainedt81. inity.Stimulated fireflies advance the phase of their 2.2 Network control inspired by biological mech- own timer by a small amount.In this way some ad- anisms vance their timer just enough to flash concurrently.By Biological systems are organized in a hierarchical stimulating each other repeatedly,they eventually be- structure:ecosystem,group,individual,organ sys- gin to flash simultaneously and at the same regular in- tem,organ,tissue,and cells.Each level or layer is terval.Pulse coupled-oscillator(PCO)is a mathemati- self-organized within the biological system.A higher cal model which explains the emergence of synchroni- layer entity is controlled and organized by interaction zation in a group of firefliess). and cooperation among lower layer entities. Since synchronization and scheduling is indispen- The immune system is a complex system to protect sable for effective and efficient network operation,sev- vertebrates from infection by pathogens.It distingui- eral control mechanisms have been developed based on shes self,such as cells from its own body,from non- the PCO model.For example,by adopting the PCO self,such as pathogens.It then attacks and eliminates model,wireless sensor nodes can schedule message e-the non-self.In contrast to primary immunity,such as missions so that they will not cause collisions among skin and gastric acid,secondary immunity has a mech- each other on the wireless channel.Additionally,ef- anism to learn and remember new pathogens and rein- fective sleep scheduling based on synchronization leads force itself.A model of the biological immune system to higher throughput,smaller delays,and longer life- called an artificial immune system (AIS)9 has been times in a wireless sensor network6 applied to detection and protection from denial-of-serv-
·372· 智能系统学报 第4卷 ice (DoS)attacks1.In this system,each node in a been proposed such as spatial time division multiple network cooperates with other nodes to learn to distin- access (S-TDMA)scheduling,routing,and con- guish between self and non-self,and to detect and tent distribution.In the case of clustering of wireless block non-self,or suspicious traffic.Security mecha- sensor networks,a spot pattern is most suitable[3]. nisms based on AIS are simple and easy to implement. For saving energy consumed in long distance transmis- By placing many detectors in a network high adaptabili- sion of wireless signals and for efficient use of wireless ty and robustness can be attained. channel capacity,neighboring nodes form a group, Living organisms such as animals and fishes have called a cluster.One representative node among them, a periodic pattern on their surface or coat.Certain pat- called a cluster head,takes responsibility for collecting terns are specific to a species and similar patterns are sensor data from the other nodes in the cluster,called generated independently of changes to the size or figure cluster members,and sends the collected data to a of an individual.Even if a part of the pattern is lost sink.To balance the energy consumption,cluster due to injury,it is eventually regenerated.Patter gen-heads should be uniformly distributed within the moni- eration is also a result of self-organizing morphogene- tored region.Therefore,a spatial distribution of cluster sis,i.e.,the chemical interaction of morphogens a-heads resembling the spot pattern of morphogen con- mong cells.A reaction-diffusion model explains the centrations is most appropriate.Since the role of clus- process of pattern generation.In this model,two hypo-ter heads should be rotated among the nodes,it is best thetical chemical substances,called an activator and to determine the initial morphogen concentrations de- an inhibitor,are synthesized,decomposed,and dif-pending on the amount of residual energy of each fused Through chemical reactions and diffusion of node.After a spot pattemn emerges,the node with the the hypothetical morphogens,a heterogeneous spatial highest morphogen concentration becomes a cluster distribution of morphogen concentrations emerges and a head in that spot,or cluster.Forwarding data from pattern is generated.Depending on the functions and cluster members to a cluster head can be accomplished parameters of the model,a variety of patterns such as by simply following the gradient of the morphogen con- mazes,spots,and stripes can be generated as shown in centration.A node sends data to the neighboring node Fig.3. with the highest morphogen concentration.Eventually, reaction-diffusion model all data reaches the node with the highest morphogen -F(u.v)+D.V -G(u.v)+D.Vv concentration in the cluster-the cluster head. at reaction diffusion All bio-inspired network control mechanisms intro- w activator v inhitior D.,D.diffustion duced in this section are based on the four previously coeffcient mentioned principles of self-organization.For example, sink in a reaction-diffusion based clustering mechanism, ○cluster head cluster nodes interact with each other through diffusion of mor- clustering phogens.This results in positive and negative feedback in the chemical reactions of the morphogens,resulting Fig.3 Reaction-diffusion based clustering in a wireless in activation and inhibition,and the pattern fluctuates sensor network.The distribution of clusters in a due to dynamically changing residual energy so that the wireless sensor network resembles a spot pattern pattern generated does not always remain the same. self-organized by the reaction-diffusion model However,there is still a lot of room for further in- Taking inspiration from self-organized pattern gen- vestigation in this field.For example,nesting of in- eration,several applications to network control have sects,schooling of fish,flocking of birds,heat shock
第4期 Naoki WAKAMIYA,et al:Biologically inspired self-organizing networks ·373· responses,cell differentiation and biological symbiosis The deterministic control function f is multiplied can also provide basic models for self-organizing net- with a parameter,called activity,which corresponds to work control mechanisms the growth rate of the cell.When an appropriate attract- or,i.e.,a stable gene expression state for the current 3 Noise-assisted adaptation nutrient condition is reached,the activity becomes high Biological systems are inherently noisy and within and as a result the deterministic control dominates the a group of biological organisms there are no absolutely dynamics of Y so that its state remains at this attractor in identical individuals.Cells constituting a tissue are dif- spite of existing fluctuations.However,once the nutri- ferent from each other in terms of the amount of sub- ent conditions change and the chosen attractor becomes stances,even if they all play the same role.Further- no longer suitable,activity decreases and the noise term more,biological systems continuously keep changing is dominating.The system begins to look for a new good and even the level of diversity within the population attractor by randomly searching in the phase space. does not stay the same.As stated in Section 1,noise When it eventually approaches a suitable attractor,the or fluctuation is one of the main principles for self-or- activity begins to increase again and the deterministic ganization.It helps a system to leap from local minima control driving the gene expression X towards the good and adapt to new environments. attractor is reinforced,see Fig.4 and 5. environment changes 1.0 good atractor changes 0.9 0.8 Hig、 0.7 di-f(X)Xa*刀 d 0.6 random deterministic N 0.5 control】 control attractor activity decreases 0.4 system state random walk and 0.3 finding new attractor 0.2 0.1 Low Fig.4 Attractor selection model.The system is driven by 0.20.40.6 0.81.0 fluctuations to find a new good attractor. activity The attractor selection scheme is a model of the Fig.5 Attractor selection-based multipath routing.As the adaptation mechanism in the genetic expression of E. activity becomes high,one appropriate path is pref- coli cells as they respond to environmental changes in erably chosen with a higher selection probability nutrient concentration4.Although a cell may not Future information networks will often face unex- have signal transduction pathways for adapting to all pected,unpredicted,and irresolvable conditions due possible events occurring outside,it can automatically to the number of connected users and devices,the di- adjust its state of gene expression in order to increase versity in usage,behavior,and traffic patterns,as well its activity or growth rate when facing an environment as their temporal variations.Therefore,a conventional with very low nutrient levels.The stochastic Langevin- design methodology,which prepares for recovery and type of differential equation shown below describes how adaptation of predictable failures and changes,is no the dynamics of the messenger RNA (mRNA)concen- longer valid.The attractor selection model is a power- tration X in an E.coli cell is composed of a determinis- ful means of making a network adaptive and robust in tic control function and a term reflecting the inherent such environments,since it does not require any pre- noise in gene expression. configured recovery and adaptation mechanisms.It has dx =f(X)xa+n been applied to routing and topology controls,for ex- dt