Self Organising Communication Networks in an Amorphous Computer

Amorphous computing and MEMs research will enable novel applications of computing coupled with the environment. For example smart paint that detects shadows on a wall, bridge surfaces that detect load, sensors that monitor chemical concentrations in the soil, or an airplane wing covered with sensors and actuators that reduce. In such environments an important goal is to self-organise global information through collaboration between large number of elements, each of which has limited resources and little global knowledge.

Communication is an important problem. Most algorithms for control require some communication beyond the local neighbors. In such environments with so many components, human intervention is not possible. It is not possible to incrementally add pieces, or assign IP addresses from a centralized source. Therefore the communication network must self organise and be self repairing.

Self Organising Area Network

Daniel Coore, Radhika Nagpal, Ron Weiss

An area network uses the Post Office paradigm. The components are divided into cities, cities collect to form states, states form countries etc. Each group or area has its main post office. If I want to route a message that does not belong to my city I hand it to the city post office. The city post office knows all the cities in this state. If it does not belong to this state its hands it to the state office who them checks neighboring statse and so on. Thus routing is by group affliliation. Examples of such networks are the internet and telephone network.

We have designed a self organising area network where individual processors organise into groups and choose group leaders. The groups then coordinate through their leaders to act as a single units. A heirarchy of groups can be created by recursively running group forming algorithms. In AI Memo 1614 we describe several algorithms for creating groups of fixed diameter and with the correct properties for a network. The picture shows a two level heirarchy - the circles represent the first level groups (which can overlap) and the groups with the same color are connected via a tree in the second level grouping.

Emergent Communication Networks

Radhika Nagpal

For sensor based applications, group based (or heirarchical) networks are not necessarily the best answer. The main reason is that they are static - the grouping is done apriori without any knowledge of the ultimate traffic pattern that may run on top of it.

Rather than have a comprehensive structure that is created apriori, have structures that emerge in response to a need - in this case the need to communicate. Such a structure can optimize for the current need. In addition, the fact that the structure already emerges and adapts to the traffic pattern makes it easier to extend it to change and adapt to other conditions, like failures and congestion, as well.

An Emergent Network uses a very simple strategy for building such a system. When a source needs to communicate with a destination, it first searches for the destination by sending out a search message. The search message accumulates knowledge of its paths as it travels. When the destination recieves the search msg, it responds to the first such search message (assuming that since this message arrived first it travelled along the faster path) by sending back a path setup msg along the path the search msg travelled. As the path setup travels back to the source it sets up routing table entries pointing to the destination. in each of the processors through with it travels. One can think of this as ants laying down pheromones from a food source so that subsequent ants can get there. Once a path is set up the source can then use that path for subsequent messages to that destination.

Each processors has a limited amount of memory allocated for routing tables - hence every processor is a potential router. A path setup message marks processors it passes through with an entry for the destination. Reuse of a path by messages re-enforces a path. If the table is full the LRU entry is replaced. In this way old paths get forgotten over time in favor of current paths. Broken paths, either because a processor no longer has the routing entry or the next processor does not respond, can be corrected by initiating a limited range search for either processors that know the path to the destination, or for the destination.

The search is performed by generating a search wave, which is similar to a bfs tree generated from the source, or like a forest fire that travels radially away from the source. The advantage of using a wave is that it finds close to the shortest path (it may not be the shortest because of asychronicity in messages but it is close) in isolation. When there is congestion along the way, the wave gets dampened in that direction by the messages getting delayed. Hence it also responds to congestion existing in the system. The search message itself adds to congestion therefore one can perform limited range searchs, or if the algorithm has some apriori knowledge of the proximity of the destination that can be incorporated.

The emergent communication structure has many desirable propeties. It choses efficient paths that try to minimize the distance travelled between source and destination and chose the path with the fastest time response and therefore less congestion. Also it automatically creates a network structure that is tailored to the application structure by reflecting the communication pattern. Rather then creating a specialized network for each of these applications the emergent network automatically evolves the correct network structure for the problem.

This picture shows a search wave. The maximum congestion (dark red) occurs along the end of the search wave.

In this picture the fastest path found avoids the existing area of congestion.

4 Squares

In this simulation there are four main actuators that talk to each other
and receive messages from all the sensors in their regions.



Tree Communication

There is a single control center to which all nodes covey messages at different frequencies.