Influences on the formation and evolution of Physarum polycephalum inspired emergent transport networks

The single-celled organism Physarum polycephalum efficiently constructs and minimises dynamical nutrient transport networks resembling proximity graphs in the Toussaint hierarchy. We present a particle model which collectively approximates the behaviour of Physarum. We demonstrate spontaneous transport network formation and complex network evolution using the model and show that the model collectively exhibits quasi-physical emergent properties, allowing it to be considered as a virtual computing material. This material is used as an unconventional method to approximate spatially represented geometry problems by representing network nodes as nutrient sources. We demonstrate three different methods for the construction, evolution and minimisation of Physarum-like transport networks which approximate Steiner trees, relative neighbourhood graphs, convex hulls and concave hulls. We extend the model to adapt population size in response to nutrient availability and show how network evolution is dependent on relative node position (specifically inter-node angle), sensor scaling and nutrient concentration. We track network evolution using a real-time method to record transport network topology in response to global differences in nutrient concentration. We show how Steiner nodes are utilised at low nutrient concentrations whereas direct connections to nutrients are favoured when nutrient concentration is high. The results suggest that the foraging and minimising behaviour of Physarum-like transport networks reflect complex interplay between nutrient concentration, nutrient location, maximising foraging area coverage and minimising transport distance. The properties and behaviour of the synthetic virtual plasmodium may be useful in future physical instances of distributed unconventional computing devices, and may also provide clues to the generation of emergent computation behaviour by Physarum.     

Applications of multi-agent slime mould computing

The giant single-celled slime mould Physarum polycephalum has inspired rapid developments in unconventional computing substrates since the start of this century. This is primarily due to its simple component parts and the distributed nature of the ‘computation’ which it approximates during its growth, foraging and adaptation to a changing environment. Slime mould functions as a living embodied computational material which can be influenced (or programmed) by the placement of external stimuli. The goal of exploiting this material behaviour for unconventional computation led to the development of a multi-agent approach to the approximation of slime mould behaviour. The basis of the model is a simple dynamical pattern formation mechanism which exhibits self-organised formation and subsequent adaptation of collective transport networks. The system exhibits emergent properties such as relaxation and minimisation and it can be considered as a virtual computing material, influenced by the external application of spatial concentration gradients. In this paper we give an overview of this multi-agent approach to unconventional computing. We describe its computational mechanisms and different generic application domains, together with concrete example applications of material computation. We examine the potential exploitation of the approach for computational geometry, path planning, combinatorial optimisation, data smoothing and statistical applications.     

Fault tolerant network design inspired by Physarum polycephalum

Physarum polycephalum, a true slime mould, is a primitive, unicellular organism that creates networks to transport nutrients while foraging. The design of these natural networks proved to be advanced, e.g. the slime mould was able to find the shortest path through a maze. The underlying principles of this design have been mathematically modelled in literature. As in real life the slime mould can design fault tolerant networks, its principles can be applied to the design of man-made networks. In this paper, an existing model and algorithm are adapted and extended with stimulation and migration mechanisms which encourage formation of alternative paths, optimize edge positioning and allow for automated design. The extended model can then be used to better design fault tolerant networks. The extended algorithm is applied to several national and international network configurations. Results show that the extensions allow the model to capture the fault tolerance requirements more accurately. The resulting extended algorithm overcomes weaknesses in geometric graph design and can be used to design fault tolerant networks such as telecommunication networks with varying fault tolerance requirements.     

Are motorways rational from slime mould's point of view?

We analyse the results of our experimental laboratory approximation of motorway networks with slime mould Physarum polycephalum. Motorway networks of 14 geographical areas are considered: Australia, Africa, Belgium, Brazil, Canada, China, Germany, Iberia, Italy, Malaysia, Mexico, the Netherlands, UK and USA. For each geographical entity, we represented major urban areas by oat flakes and inoculated the slime mould in a capital. After slime mould spanned all urban areas with a network of its protoplasmic tubes, we extracted a generalised Physarum graph from the network and compared the graphs with an abstract motorway graph using most common measures. The measures employed are the number of independent cycles, cohesion, shortest paths lengths, diameter, the Harary index and the Randi? index. We obtained a series of intriguing results, and found that the slime mould approximates best of all the motorway graphs of Belgium, Canada and China, and that for all entities studied the best match between Physarum and motorway graphs is detected by the Randi? index (molecular branching index).     

自适应波束天线自组网拓扑控制算法

定向天线能显著提高无线系统的性能和容量,但采用定向天线的自组网拓扑构建问题比全向天线网络复杂。拓扑控制是一种保证网络连通和性能优化的有效手段。基于自适应波束定向天线模型提出一种拓扑控制算法,确定天线的主波束朝向,调整节点的发射功率构建拓扑。算法在保证网络连通的基础上,利用主波束的高增益,降低了节点的发射功率,从而降低节点能耗;同时利用定向天线方向性强的特点,减少了节点间干扰,提高了网络吞吐量。仿真结果表明,算法显著提高了网络性能。     

增强Ad Hoc网络可靠性的管理机制

基于网络拓扑的动态感知,提出一个综合考虑网络拓扑连通性、网络被破坏程度及连通分支内部结构的网络抗毁性定量评估模 型——网络抗毁率EFF(G)和一种面向Ad Hoc网络分布式实施的增强网络可靠性的策略管理机制——感知拓扑的抗毁可靠管理机制,通过实例分析证明EFF(G)是一种有效的网络抗毁性评估测度。     

平均度约束的无线传感器网络拓扑控制

拓扑控制是无线传感器网络中最重要的技术之一.大规模随机部署的无线传感器网络节点,在满足无线传感器网络拓扑连通性的前提下,如何保证网络结构的稀疏性是一个亟待解决的问题,目前已有的研究结果表明当节点密度较大时,得到的网络拓扑复杂,计算路由将严重消耗节点资源.文中提出了一种平均度约束的无线传感器网络拓扑控制,通过增加节点通信半径,约束节点的平均度来解决网络的连通性与网络拓扑的稀疏性之间的矛盾.数值模拟表明:通过平均度约束的无线传感器网络拓扑控制,可减少网络中选出的工作节点数,保证了网络的稀疏性,简化了路由的复杂度,从而延长了网络的生存周期.     

On creativity of slime mould

Slime mould Physarum polycephalum is large single cell with intriguingly smart behaviour. The slime mould shows outstanding abilities to adapt its protoplasmic network to varying environmental conditions. The slime mould can solve tasks of computational geometry, image processing, logics and arithmetics when data are represented by configurations of attractants and repellents. We attempt to map behavioural patterns of slime onto the cognitive control vs. schizotypy spectrum phase space and thus interpret slime mould’s activity in terms of creativity.     

A systematic approach to constructing incremental topology control algorithms using graph transformation

Communication networks form the backbone of our society. Topology control algorithms optimize the topology of such communication networks. Due to the importance of communication networks, a topology control algorithm should guarantee certain required consistency properties (e.g., connectivity of the topology), while achieving desired optimization properties (e.g., a bounded number of neighbors). Real-world topologies are dynamic (e.g., because nodes join, leave, or move within the network), which requires topology control algorithms to operate in an incremental way, i.e., based on the recently introduced modifications of a topology. Visual programming and specification languages are a proven means for specifying the structure as well as consistency and optimization properties of topologies. In this paper, we present a novel methodology, based on a visual graph transformation and graph constraint language, for developing incremental topology control algorithms that are guaranteed to fulfill a set of specified consistency and optimization constraints. More specifically, we model the possible modifications of a topology control algorithm and the environment using graph transformation rules, and we describe consistency and optimization properties using graph constraints. On this basis, we apply and extend a well-known constructive approach to derive refined graph transformation rules that preserve these graph constraints. We apply our methodology to re-engineer an established topology control algorithm, kTC, and evaluate it in a network simulation study to show the practical applicability of our approach.     

Structural machines and slime mould computation

A Physarum machine is a programmable amorphous biological computer experimentally implemented in the vegetative state of true slime mould Physarum polycephalum. It comprises an amorphous yellowish mass with networks of protoplasmic veins, programmed by spatial configurations of attracting and repelling gradients. The goal of this paper to advance formalism of Physarum machines providing theoretical tools for exploration of possibilities of these machines and extension of their applications. To achieve this goal, we introduce structural machines and study their properties.     

A Physarum-inspired approach to supply chain network design基于多头绒泡菌模型的供应链网络设计算法

A supply chain is a system which moves products from a supplier to customers, which plays a very important role in all economic activities. This paper proposes a novel algorithm for a supply chain network design inspired by biological principles of nutrients’ distribution in protoplasmic networks of slime mould Physarum polycephalum. The algorithm handles supply networks where capacity investments and product flows are decision variables, and the networks are required to satisfy product demands. Two features of the slime mould are adopted in our algorithm. The first is the continuity of flux during the iterative process, which is used in real-time updating of the costs associated with the supply links. The second feature is adaptivity. The supply chain can converge to an equilibrium state when costs are changed. Numerical examples are provided to illustrate the practicality and flexibility of the proposed method algorithm.     

Ad Hoc网络中基于测度的冲突受限算法

拓扑控制一直是Ad Hoc网络中的研究热点,文章给出了一种新的冲突受限模型,从测度的角度对冲突进行定量的分析描述,并提出基于测度的冲突受限算法(ICBM)。该算法在保证网络连通性的前提下构建了一个冲突控制拓扑。仿真结果显示ICBM有效地降低了网络冲突,提高了网络性能。     

Asymptotically optimal trade-off between local and global connectivity in wireless networks

We analyze large, random network topologies that arise in ad hoc or sensor networks. A fundamental requirement of communication in these systems is reachability, that is, to have a connected network topology. It is known, however, that the price for full connectivity is very high, as it requires unbounded local complexity, i.e., it forces the nodes to have infinitely growing degrees to achieve asymptotic connectivity. This means a lack of scalability, which is known to hold for a quite general class of random network topology models. Therefore, an important step in analyzing the performance of such networks is to explore the trade-off between the fraction of nodes that still belong to a connected component vs. a bound imposed on local connectivity, i.e., on the node degrees. We investigate this issue in a model that is more general than previously investigated random wireless network topology models. In our general model we derive an asymptotically optimal trade-off between node degrees and the fraction of nodes that form a connected component.     

一种保持Ad hoc网络拓扑特性的拓扑维护策略

无线Ad hoc网络中在结点发生异动的情况下,通常采用局部网络的重构来维持网络的连通性。提出了一个能保证网络连通,维持拓扑结构性能的拓扑维护策略,该策略能够为基于位置信息的拓扑控制算法增加自维护功能。理论分析和实验表明,新的策略只需增加一定维护开销,即可保持拓扑结构在结点度、功率有效性、能耗扩展因子等方面的最佳性能。     

A Combinational Perspective in Stimulating Cooperation in Mobile Ad Hoc Networks

In wireless ad hoc networks cooperation among nodes cannot always be assumed since nodes with limited resources and different owners are capable of making independent decisions. Cooperation problems in topology control and packet forwarding tasks have been mostly studied separately but these two tasks are not independent. Considering a joint cooperation problem by taking into account dependencies between tasks will result in more reliable and efficient networks. In this paper topology control definition is extended to cover cooperation problem in both packet forwarding and topology control in a single problem. In this definition nodes have to adjust their transmission power and decide on their relay role. This paper models the interactions of nodes as a potential game with two-dimensional utility function. The presented model, named TCFORCE (Topology Control packet FORwarding Cooperation Enforcement), preserves the network connectivity and reduces the energy consumption by providing cooperative paths between all pairs of nodes in the network.     

一种基于构件技术实现物理网络拓扑发现的方法

物理网络拓扑指的是一个通讯网内部实体的物理实际链接,准确自动获取物理网络拓扑图是完成许多重要网络管理任务的前提。以物理网络拓扑发现构件设计与实现过程为例,以UML为建摸语言,介绍了一种利用设计模式设计构件具体功能的方法。     

基于网络编码的分层P2P网络的拓扑感知算法研究

网络编码是一种可改进网络吞吐率和可靠性的新兴技术。然而,这些优势极大地受制于网络拓扑结构,在P2P网络中尤为如此。通过精确的拓扑感知,可以在吞吐率和可靠性方面帮助改进使用网络编码的系统性能。本文提出了一种新颖的基于网络编码回馈的拓扑感知机制(TANCF)来进行网络拓扑感知。该机制利用层次化网络中节点的回馈来探测信源到节点的可达路径信息,而根据可达路径信息与关联矩阵的密切关系,可构建关联矩阵并优化网络编码系统的参数。在理论分析中,我们推导出了该机制的解码概率方程以及正常运行的可行条件。通过仿真实验,我们进一步验证了该机制的可行性。     

Jurisdictional Control and Network Growth

Transport infrastructure evolves over time in a complex process as part of a dynamic and open system including travel demand, land use, as well as economic and political initiatives. As transport infrastructure changes, each traveler may adopt a new schedule, frequency, destination, mode, and/or route, and in the long term may change the location of their activities. These new behaviors create demand for a new round of modifications of infrastructure. In the long run, we observe the collective change in the capacity, service, connectivity, and connection patterns (topology) of networks. This paper examines how a fixed set of places incrementally gets connected as transport networks are constructed and upgraded over time. A simulator of network incremental connection (SONIC) is constructed to model the process of incremental connections and examines how networks evolve differently under centralized versus decentralized jurisdictional initiatives. Exploring the mechanism underlying this dynamic process can answer questions such as how urban networks have developed into various topologies, which network patterns are more efficient, and whether and how transport engineers, planners, and decision makers can guide the dynamics of land uses and infrastructure in a desired direction.     

基于局部估计的功率驱动多智能体网络牵制蜂拥控制算法

针对复杂功率驱动系统控制中现有牵制控制策略在保持拓扑结构连通性和降低功率消耗方面存在的不足,提出一种基于局部估计的功率驱动多智能体网络的牵制蜂拥控制算法。该算法首先利用幂迭代一致估计算法动态估计多智能体网络的代数连通度;然后根据代数连通度的局部估计值及最大功率约束自适应调整个体发射半径,以保持多智能体网络在演化过程中拓扑结构的连通性,并有效降低功率消耗;最后通过仿真实验验证了所提出控制算法的有效性。     

A morphological adaptation approach to path planning inspired by slime mould

Path planning is a classic problem in computer science and robotics which has recently been implemented in unconventional computing substrates such as chemical reaction–diffusion computers. These novel computing schemes utilise the parallel spatial propagation of information and often use a two-stage method involving diffusive propagation to discover all paths and a second stage to highlight or visualise the path between two particular points in the arena. The true slime mould Physarum polycephalum is known to construct efficient transport networks between nutrients in its environment. These networks are continuously remodelled as the organism adapts its body plan to changing spatial stimuli. It can be guided towards attractant stimuli (nutrients, warm regions) and it avoids locations containing hazardous stimuli (light irradiation, repellents, or regions occupied by predatory threats). Using a particle model of slime mould we demonstrate scoping experiments which explore how path planning may be performed by morphological adaptation. We initially demonstrate simple path planning by a shrinking blob of virtual plasmodium between two attractant sources within a polygonal arena. We examine the case where multiple paths are required and the subsequent selection of a single path from multiple options. Collision-free paths are implemented via repulsion from the borders of the arena. Finally, obstacle avoidance is implemented by repulsion from obstacles as they are uncovered by the shrinking blob. These examples show proof-of-concept results of path planning by morphological adaptation which complement existing research on path planning in novel computing substrates.