Description and composition of bio-inspired design patterns: a complete overview <s> Spreading pattern <s> Choosing appropriate information dissemination strategies is crucial in mobile ad hoc networks (MANET) due to the frequent topology changes. Flooding-based approaches like diffusion have a strong similarity with epidemic spreading of diseases. Applying epidemiological models to information diffusion allows the evaluation of such strategies depending on the MANET characteristics, e.g. the node density. In order to choose appropriate strategies at run time, the model should be easily evaluated.In this paper, an epidemic model is developed for a simple information diffusion algorithm based on simulation results. We analytically investigate the impact of node density on information diffusion. The analytical model allows the evaluation at runtime, even on devices with restricted resources, and thus enables mobile nodes to dynamically adapt their diffusion strategies depending on the local node density. <s> BIB001 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Spreading pattern <s> Broadcasting is a common operation in a network to resolve many issues. In a mobile ad hoc network (MANET) in particular, due to host mobility, such operations are expected to be executed more frequently (such as finding a route to a particular host, paging a particular host, and sending an alarm signal). Because radio signals are likely to overlap with others in a geographical area, a straightforward broadcasting by flooding is usually very costly and will result in serious redundancy, contention, and collision, to which we call the broadcast storm problem. In this paper, we identify this problem by showing how serious it is through analyses and simulations. We propose several schemes to reduce redundant rebroadcasts and differentiate timing of rebroadcasts to alleviate this problem. Simulation results are presented, which show different levels of improvement over the basic flooding approach. <s> BIB002 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Spreading pattern <s> Modern UAV’s reduce the threat to human operators, but do not decrease the manpower requirements. Each aircraft requires a flight crew of one to three, so deploying large numbers of UAV’s requires committing and coordinating many human warfighters. Insects perform impressive feats of coordination without direct inter-agent coordination, by sensing and depositing pheromones (chemical scent markers) in the environment [14]. We have developed a novel technology for coordinating the movements of multiple UAV’s based on a computational analog of pheromone dynamics. The control logic is simple enough that it can be executed autonomously by a UAV, enabling a single human to monitor an entire swarm of UAV’s. This paper describes the technology, its application to UAV coordination, and the results we have obtained. <s> BIB003 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Spreading pattern <s> The blind flooding can become very inefficient because of redundant, "superfluous" forwarding. In fact, superfluous flooding increases link overhead and wireless medium congestion. In a large network, with heavy load, this extra overhead can have severe impact on performance and should be eliminated. Efficient flooding schemes to choose a dominant set of nodes have been recently proposed in ad hoc networks. In this paper, we compare the performance of a set of representative schemes via simulation using as criteria the flooding efficiency and the delivery ratio. <s> BIB004 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Spreading pattern <s> We present a new information dissemination protocol for wireless sensor networks. This protocol uses location information to reduce redundant transmissions, thereby saving energy. The sensor network is divided into virtual grids and each sensor node associates itself with a virtual grid based on its location. Sensor nodes within a virtual grid are classified as either gateway nodes or internal nodes. While gateway nodes are responsible for forwarding the data across virtual grids, internal nodes forward the data within a virtual grid. The proposed approach, termed location-aided flooding (LAF), achieves energy savings by reducing the redundant transmissions of the same packet by a node. We study the performance of LAF for different grid sizes and different node densities and compare it to other well-known methods. We show that LAF can save a significant amount of energy compared to prior methods. <s> BIB005
The Spreading Pattern is based on direct communication among agents for progressively sending information over the system. The spreading of information in multi-agent systems allows the agents to increment the global knowledge of the system. Figure 5 shows the different steps of the spreading process: (a) an agent initiates the spreading process (black node); (b) the information spreads over the network; and (c) the process finishes when information reaches all the nodes in the network. Aliases: spreading is also known as information diffusion BIB001 , information or data dissemination BIB005 , flooding BIB004 , broadcast BIB002 , or epidemic spreading BIB001 . Problem: in systems, where agents perform only local interactions, agents' reasoning suffers from the lack of knowledge about the global system. Solution: a copy of the information (received or held by an agent) is sent to neighbours and propagated over the network from one node to another. Information spreads progressively over the system and reduces the lack of knowledge of the agents while keeping the constraint of the local interaction. Inspiration: spreading is a basic pattern extended or exploited by most other patterns presented in this catalogue. Spreading appears in important processes, such as, Morphogenesis, Chemotaxis or Quorum Sensing (Sect. 5.3) In nature, spreading is a process done by the environment. Forces: if spreading occurs with high frequency, the information spreads over the network quickly but the number of messages increases. A quick spread is desired when the environment is continuously changing and the agents must know the new values and adapt themselves. It may happen that the information is only interesting for agents close to the source. In that case, the information spreads only up to a determined number of hops, reducing the number of messages. Another way to reduce the number of messages is to determine the number of neighbouring nodes that receive the information. It was demonstrated that it is not necessary to send the information to all the neighbouring nodes in order to ensure that every node has received the information (Birman et al. 1999) . Entities-Dynamics-Environment: the entities involved in the spreading process are the hosts, agents, and infrastructural agents. The spreading process is initiated by an agent that first spreads the information in the host it is residing in. When this information arrives to neighbouring nodes, the infrastructural agent is in charge to re-send the information to neighbouring nodes, producing the spreading of the information over the whole system. Each infrastructural agent forwards the information received to a specified number of neighbours and up to the specified number of hops. The dynamics is usually extended to avoid infinite loops and wasted duplicate deliveries (e.g. when one agent receives the same information it has sent before, the agent does not resend that information). Transition Rule (1)  A function m(L) is given for determining the sequence of locations, among the neighbours of L, to which the information in input has to be spread. The set of such locations cannot be empty, cannot be composed of L only, but can be composed of all the neighbourhood of L including L itself. A function r(C, L) is given for computing the new information content, which may change within the spreading process. Implementation: the most common algorithm used to spread the information to the neighbours is the broadcast algorithm. It is well known that broadcast causes what is called as the Broadcast Storm Problem BIB002 . The Broadcast Storm Problem appears when the radius of the signal of many nodes overlaps. Thus, a straightforward broadcasting by flooding will result in serious redundancy, contention and collision. In order to solve the Broadcast Storm Problem, an optimised broadcast can be implemented, which can follow a probabilistic, counter-base, distance-base, location-base or cluster-base schema BIB002 . As time goes by, new proposals for efficient ways of spreading the information are proposed. This work presents a basic implementation to illustrate how spreading works and how it has been implemented in the literature. Further comparison between different kinds of spreading implementations and their performances is out of the scope of this work. Figure 5a shows the flow chart where the information spreads after it is received. Figure 5b shows the interaction diagram of the spreading initialisation. Figure 5c represents the interactions when the information arrives to a neighbour. Known uses: the spreading mechanism has been applied to several applications: Swarm motion coordination BIB003 , coordination in games , and problem optimisation (Blu 2005). More references of applications can be found in higher level patterns that exploit the Spreading Pattern (i.e. Gradient Pattern, Morphogenesis Pattern, Chemotaxis Pattern and Quorum Sensing Pattern). Consequences: when the Spreading Pattern is applied, the agents in the system sense information from beyond their local sensing. Then, there is an increment of the network load (i.e. messages and memory). This increment becomes extreme when the environment is very dynamic and the agents have to keep the information updated as soon as possible. Related Patterns: spreading is used in higher level patterns such as Gradient (Sect. 5.2.1), Morphogenesis (Sect. 5.3.3), or Chemotaxis Pattern (Sect. 5.3.2).