Description and composition of bio-inspired design patterns: a complete overview <s> Aliases: the Gradient Pattern is a particular kind of computational fields (Bea 2009) (i.e. physical fields based abstractions). <s> An ad-hoc network is the cooperative engagement of a collection of mobile nodes without the required intervention of any centralized access point or existing infrastructure. We present Ad-hoc On Demand Distance Vector Routing (AODV), a novel algorithm for the operation of such ad-hoc networks. Each mobile host operates as a specialized router, and routes are obtained as needed (i.e., on-demand) with little or no reliance on periodic advertisements. Our new routing algorithm is quite suitable for a dynamic self starting network, as required by users wishing to utilize ad-hoc networks. AODV provides loop-free routes even while repairing broken links. Because the protocol does not require global periodic routing advertisements, the demand on the overall bandwidth available to the mobile nodes is substantially less than in those protocols that do necessitate such advertisements. Nevertheless we can still maintain most of the advantages of basic distance vector routing mechanisms. We show that our algorithm scales to large populations of mobile nodes wishing to form ad-hoc networks. We also include an evaluation methodology and simulation results to verify the operation of our algorithm. <s> BIB001 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Aliases: the Gradient Pattern is a particular kind of computational fields (Bea 2009) (i.e. physical fields based abstractions). <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> BIB002 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Aliases: the Gradient Pattern is a particular kind of computational fields (Bea 2009) (i.e. physical fields based abstractions). <s> To support and engineer the spatial coordination of distributed pervasive services, we propose a chemical-inspired model, which extends tuple spaces with the ability of evolving tuples mimicking chemical systems, that is, in terms of reaction and diffusion rules that apply to tuples modulo semantic match. The suitability of this model is studied by considering a self-adaptive display infrastructure providing people nearby with several visualization services (advertisements, news, personal and social content). The key result of this article is that general-purpose chemical reactions inspired by population dynamics can be used in pervasive applications to enact spatial computing patterns of competition and gradient-based interaction. <s> BIB003
Problem: agents belonging to large systems suffer from lack of global knowledge to estimate the consequences of their actions or the actions performed by other agents beyond their communication range. Solution: information spreads from the location it is initially deposited and aggregates when it meets other information. During spreading, additional information about the sender's distance and direction is provided: either through a distance value (incremented or decremented); or by modifying the information to represent its concentration (lower concentration when information is further away). Thus, agents that receive gradients have information that come from beyond their communication range, increasing the knowledge of the global system not only with gradients information but also with the direction and distance of the information source. During the aggregation process, a filter operator keeps only the information with the highest (or lowest) distance, or it modifies the concentration. Gradients can deal with network topology changes. In this case the information spreads periodically and is subject to evaporation, reducing its relevance along the time, and enabling the gradients to adapt to networks topology changes. Such gradients are called active gradients  . Inspiration: gradients appear in many biological processes. The most known are Ant Foraging, Quorum Sensing, Morphogenesis, and Chemotaxis processes. In these processes, gradients support long-range communication among entities (cells, bacteries, etc..) through local interaction. Forces: adaptation to environmental changes is faster when updating frequencies are high, thus increasing network overload. Lower updating frequencies reduce network overload, but can lead to outdated values when environmental changes occur. There is a trade-off between the diffusion radius (number of hops) and the load in the network. A higher diffusion radius brings information further away from its source, providing guidance to distant agents. However, it increments the load and may overwhelm the network (Bea 2009). Entities-Dynamic-Environment: entities acting in the Gradient Pattern are Agents, Hosts, and Infrastructural Agents. Analogously to the Spreading Pattern, when a gradient is created, it is spread to its neighbours. The transition rules for the Gradient Pattern are specific instances of Transition Rule (1) and Transition Rule (2). An example is given in Transition Rules (7). We assume that each tuple contains a D attribute that represent the distance from the current host to the source of the gradient. The first transition rule models the spreading of information modifying the distance attribute by incrementing or decrementing its value so to get to a cone-shaped gradient with the vertex down or up. Moreover, the rule specifies a specific instance of the function m(L) introduced in Transition Rule (1) for determining the sequence of locations, among the neighbours of L, to which the information in input has to spread. Such a function randomðfL 1 ; . . .; L n gÞ chooses randomly one location among all the neighbouring locations of L. The second transition rule models the corresponding case of aggregation when multiple tuples with the same content but different distance attribute are locally present. This particular rule models the case of an aggregation where only the information with the shortest / longest distance is kept. It is important to note that D could also represent concentrations instead of distances. Implementation: agents start the process by sending information to all their neighbours, as shown in Fig. 11 b for the case with distance value. When one agent receives the information it increments the distance attribute, or it reduces accordingly the concentration value of the information, and forwards the gradient again to all its neighbours (Spreading Pattern) as shown on diagram flow Fig. 11a and sequence diagram Fig. 11b for the case with distance value. When a host receives the gradient, infrastructural agents spread it further. Notice that this pattern can be also executed by agents. When an agent receives more than one gradient, it employs aggregation (Aggregation Pattern) as shown on sequence diagram Fig. 11c . For instance, it may filter only the gradient with the lowest distance attribute. Self-healing gradients (i.e. gradients that adapt to network changes) and their implementations are proposed in (Beal et al. 1969 (Beal et al. -1975 BIB003 . Known uses: the Gradient Pattern has been used in problems such as coordination of swarms of robots BIB002 , coordination of agents in video games , or routing in AD-HOC networks BIB001 . Consequences: the Gradient Pattern adds an extra information (distance). Distance can be used to limit the number of hops during the spreading process. Related Patterns: the Gradient Pattern is a composition of the Spreading and Aggregation Patterns, extended with the distance value or concentration information. It is used by the Morphogenesis Pattern (Sect. 5.3.3), the Chemotaxis Pattern (Sect. 5.3.2), and the Quorum Sensing Pattern (Sect. 5.3.4). The Gradient Pattern may be combined with the Evaporation Pattern to create active gradients to support adaptation when agents change theirs positions or network topology changes.