第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
.374 智能系统学报 第4卷 ample,an attractor selection-based routing mechanism References outperformed other conventional routing mechanisms in unreliable and unstable wireless network scenarios. [1]BONABEAU E,DORIGO M,THERAULAZ G.Swarm in- telligence:from natural to artificial systems[M].Oxford 4 Conclusion Oxford University Press,1999:251-257. Information networks that have been designed, [2]DORIGO M,STUTZLE T.Ant colony optimization [M]. Cambridge:The MIT Press,2004:152-164. built,and operated based on self-organizing biological [3]Di CARO G,DORIGO M.AntNet:distributed stigmergetic models achieve a high level of scalability,adaptability, control for communications networks[J].Journal of Artifi- and robustness.Some biological mechanisms intro- cial Intelligence Research,1998,9:317-365. duced in this paper are modeled by nonlinear temporal [4]STROGATZ S.Sync:the emerging science of spontaneous differential equations.The formalism available through order[M].New York Hyperion press,2003:54-61. these equations permits a mathematical and theoretical [5]MIROLLO R E,STROGATZ S H.Synchronization of pulse- treatment and analysis of the stability and convergence coupled biological oscillators[J].SIAM J Applied Mathe- properties of bio-inspired networks.Furthermore,we matic8,1990,26(6):1645-1662. should design and build network control mechanisms by [6]WAKAMIYA N,MURATA M.Synchronization-based data extending models from mathematical biology,exploiting gathering scheme for sensor networks[J].IEICE Trans on Commun,2005,E88-B(3):873-881. well established theories from physics and mathemat- [7]BONABEAU E,SOBKOWSKI A,THERAULAZ G,DE- ics,not merely mimicking or imitating the behavior of NEUBOURG J L.Adaptive task allocation inspired by a actual biological systems. model of division of labor in social insects[C]//Proceed- However,we should also note that the self-organi- ings of BCEC97.Skovde,Sweden,1997:36-45. zation mechanisms mentioned in this paper are,on [8]SASABE M,WAKAMIYA N,MURATA M,MIYAHARA their own,not fully sufficient to establish scalable,a- H.Effective methods for scalable and continuous media daptive,and robust information networks,which pro- streaming on peer-to-peer networks[J].European Transac- vide users and applications with network services ap- tions on Telecommunications,2004,15:549-558. propriate for levels of demand and environmental condi- [9]DASGUPTA D.Artificial immune systems and their applica- tions[M].[S.1.]:Springer,1998:36-40. tions.We also need to develop,for example,self-con- [10]HOFMEYR S A,FORREST S.Architecture for an artifi- figuration mechanisms which recognize current system cial immune system[J].Evolutionary Computation,2000, conditions and cause the network to reconfigure itself. 8(4):443473. Furthermore,it is necessary to consider how interaction [11]TURING A M.The chemical basis of morphogenesis[J]. among different self-organizing entities may detrimen- Philosophical Transaction of the Royal Society,1952, tally affect each other and bring instability.Currently, B237:37-72, we are further investigating such mechanisms,as dis- [12]DURVY M,THIRAN P.Reaction-diffusion based trans- cussed in this paper,within the scope of the research mission patters for ad hoc networks[C]//Proceedings of IEEE INF0C0M.[S.1.],2005,3:2195-2205 projects "Special Coordination Funds for Promoting [13]WAKAMIYA N,HYODO K,MURATA M.Reaction-dif- Science and Technology:Yuragi Project"and "Global fusion based topology self-organization for periodic data COE (centers of excellence)Program for Founding gathering in wireless sensor networks[C]//Proceedings of Ambient Information Society Infrastructure"of the Min- Second IEEE International Conference on Self-Adaptive istry of Education,Culture,Sports,Science and Tech- and Self-Organizing Systems (SASO 2008).Venice,Ita- nology,Japan. 1y,2008:351-360
第4期 Naoki WAKAMIYA,et al:Biologically inspired self-organizing networks ·375· [14]KASHIWAGI A,URABE I,KANEKO K,YOMO T.A- Kenji Leibnitz is specially appointed daptive response of a gene network to environmental chan- associate professor of Graduate School of ges by fitness-induced attractor selection[J].PLoS ONE, Information Science Technology,Osaka 2006,1(1):49. University.His current research mainly [15]LEIBNITZ K,WAKAMIYA N,MURATA M.Biologically- deals with applying biologically-inspired inspired self-adaptive multi-path routing in overlay net- mechanisms to information networks. works[J].Commun,ACM,2006,49(3):62-67. Masayuki Murata is a professor of O- About the authors: saka University.His current research top- Naoki Wakamiyaisan is an associate ics include integrated multimedia QoS ar- professor of Graduate Schoolof Information chitecture,feedback mechanism in packet Science and Technology,Osaka Univer- switching networks,high-speed transport isty.He is a senior member of IEICE and architecture,high-speed packet switching architecture,Internet a member of IPSJ.ACM,and IEEE.His- traffic characterization and its application,photonic network ar- chitecture,integrated wired/wireless communication architec- research interests include overlaynetworks,sensor networks,and ture. mobile ad-hoc networks.He received the 2nd IEEE ComSoc A- sia-Pacific young researcher award in 2005. 智能科学新著介绍一《人工情感》 王志良教授编著的《人工情感》一书，已于2009年由机械工业出版社出版.该书作为“人工心理与数字 人技术丛书”之一，写作目的继续以人为本，以人与自然的和谐相处为研究目标，多学科交叉结合为研究手 段，以人工科学为主要研究领域，主要面向研究生和重点高校高年级学生 情感能力是人类智能的重要标志，是人类智能的一个不可分割的部分，它在人的感知、推理、决策、计划、 创造以及社交等诸多活动中起着不可或缺的作用.人工情感是指以人类学、心理学、脑科学、认知科学、信息 科学、人工智能等学科为理论基础，利用信息科学的手段对人类情感过程进行模拟、识别和理解，使机器能够 产生类人感情，并与人类进行自然和谐的人机交互随着智能科学、心理学、脑科学、信息科学的蓬勃发展，越 来越多的科研工作者投入到情感计算、人工情感、人工大脑、机器人、虚拟现实等多学科交叉合作研究的领 域.王志良教授在多年研究的基础上，整理编写了这本书，详细地介绍了人工情感的相关理论和算法，总结了 他所在课题组的研究成果，给出了人工情感的情感建模及应用实例. 全书共有9章.第1章主要介绍人类情绪的相关理论以及研究发展历程；第2章叙述了情绪数量化描述 的基本方法及情绪的维度理论；第3章介绍了情感建模的发展状况及前沿研究；第4章主要介绍了人工情感 数字化建模的研究新进展及应用实例；第5章介绍了情感在数字化教学系统中的应用；第6章给出了人脸识 别系统的设计范例；第7章详细介绍了表情识别系统的设计；第8章阐述了人工情感技术在游戏设计中的应 用；第9章介绍了人工情感在智能机器人中的应用， 本书适宜从事计算机、自动化、电子信息、模式识别、智能科学、人机交互技术的科研人员阅读，也可以作 为高等院校相关专业学生、研究生的教学参考书， (王志良郑思仪)