Tikalon Blog by Dev Gualtieri

Tikalon Header

Computational Biomimetics

January 17, 2011

Biomimetics has inspired more than just materials. It's inspired some computing methods as well. Genetic algorithms (GA), which take their inspiration from the way that evolution proceeds at the DNA level, are one example. Ant Colony Optimization (ACO) is another example. ACO takes its inspiration from the way that ants find a direct pathway from food to their colony. This same strategy is useful for things such as the placement of conductor traces on a printed circuit board , routing messages in a network , and solving the Travelling Salesman Problem. I wrote about ACO in a previous article (Ants in My Computer, November 8, 2006) that includes an anecdote involving an ant infestation of my keyboard. Surprisingly, what spiders do has never been important to the internet (a.k.a., the "Web"). However, another insect has entered the fray of computational biomimetics.[1] That's the fruit fly .[2-4]

As cells multiply to populate an organism, they each must determine what their specific role will be. None other than Alan Turing took an interest in one such developmental process, morphogenesis . Morphogenesis is the process by which organisms develop their particular shape. Turing was interested in how patterns form as plants and animals develop. Turing explicated the pattern-forming process as a competition between two chemical species having their own reaction and diffusion rates; in effect, he explained how the zebra gets its stripes. Turing assumed that an activator chemical can produce more of itself, but also an inhibitor, the function of the inhibitor being to destroy or stop the activity of the activator. The activator chemical, for example, can be responsible for a color change. If the inhibitor diffuses faster than the activator, a pattern will form as the chemicals diffuse through a medium.[5] Turing did this research as a way to understand why the arrangement of leaves on a plant stem seems to follow a Fibonacci number sequence , an effect called Fibonacci phyllotaxis .

In a paper just published in Science ,[2] an international research team with members from Tel Aviv University , the Institute for Advanced Study , the Weizmann Institute of Science and Carnegie Mellon University , examined how a fruit fly's nervous system "decides" which cells are to be designated as sensory organ precursors (SOPs). These SOPs then develop into the bristle-like sensory organs of the fly (see figure). The research team then used the same methods as a means of improving computer networking; most importantly, to improve wireless sensor networks . As the fruit fly nervous system develops, some leaders emerge, and one of their tasks is to tell their neighbors not to become leaders. This is similar to Turing's activator/inhibitor model.

What emerges is an efficient control system that develops without its members having any prior or present knowledge of the overall structure of the system. The network analog follows when you replace the cells by processor nodes . In the research reported in Science, single bit messages are all that are required for the leaders to generate a wireless network. Says Noga Alon, a mathematician , computer scientist and a co-author of the paper,[3-4]

"It's such a simple and intuitive solution. I can't believe we did not think of this 25 years ago."

Scanning electron micrograph of a fruit fly eye

Scanning electron micrograph of a fruit fly eye (Dartmouth College ).

This is significantly different from the traditional way of building a distributed network, which is to determine the leader nodes by their connectivity. Nodes with the greatest number of connections become the leaders. The result is a network architecture in which an optimal number of elements connect to these leader nodes, and it's just these nodes that communicate all network traffic. In graph theory , the leader nodes are called a maximal independent set . Networks established this way will work, but there is considerable messaging overhead in the initial network setup, a major problem for spectrum-starved and energy-sensitive wireless networks.

Bucking tradition, the fruit fly network team derived a fast algorithm for a fundamental distributed computing procedure that selects a set of local leaders in a network. The algorithm satisfies the fruit fly constraints that network nodes originally don't know whether they will be leaders or followers on a network. The network develops in an optimal way to select its leaders, it's robust against failure of individual elements, and it's ideal for networks for which the number of nodes and their positions are not fixed. One example of this would be a battlefield sensor network.

There is, however, a small trade-off. Network speed for the fruit fly-inspired network is slightly slower, but the network is more robust. This research was supported by the National Science Foundation and the National Institutes of Health .

References: