Subscribe Us

Get free daily email updates!

Follow us!

Monday, July 25, 2011

Ants and SON (Self Organizing Networks): Getting Ideas of Self-Organization from Ants

Our daily life is enriched—either directly or indirectly—by a considerable number of sensing, computing, controlling, or other information-processing devices, which are placed, distributed, and embedded within our environment. These devices are interconnected and organize themselves as networks to cooperate by sharing and exchanging information and controlling each other. In the future, this trend is expected to lead to an even higher level of ubiquitous and ambient connectivity.
To satisfy the wide range of users’ requirements and to support our daily life in many aspects, a variety of fixed devices including PCs, servers, home electronic appliances, and information kiosk terminals will be distributed in the environment and connected as networks. Furthermore, mobile devices that are attached to persons and vehicles, as well as small and scattered devices, such as Radio Frequency Identification (RFID) tags and sensors, will require the support of mobility from the network. All those devices generate a great variety of traffic data including voice, video, WWW/file transfer, sensory/control/management data, etc. Their characteristics may also exhibit a large diversity, such as constant/intermittent flow behavior, low/high traffic rate, and small/large volume. Even for a single application, the number, types, locations, and usage patterns of devices, as well as the condition of the communication environment, and traffic characteristics may dynamically change considerably every moment. In such an environment, a network would often face unexpected or unpredictable user behavior, usage of network, and traffic patterns, which were not anticipated at the time the network was designed or built. As the Internet itself evolved several decades ago from the ARPANET, a testbed network connecting only four nodes, it was never intended for the traffic that is currently being transported over it. With more and more additional protocols being supported, it has been “patched up” to introduce increasingly complex features.

Self-organization occurs in nature or biological systems inherently, since there is no central “leader” that determines how these systems should operate.

Ant colony optimization (ACO) is an optimization algorithm that was first proposed to obtain near-optimal solutions in self-organizing related problems. The algorithm takes inspiration from the foraging behavior of ants, that is, pheromone trails. Without a centralized control mechanism, ants establish the shortest path between their nest to a food source. The mechanism is explained as follows. Ants come out of the nest and randomly walk around to find food. When an ant finds food, it returns to the nest leaving a small amount of a chemical substance called pheromone. The pheromone left on the ground attracts other wandering ants and guides them to the food. Those guided ants reaching the food also leave the pheromone while carrying food back to the nest, and the pheromone trail is thus reinforced. Since the pheromone evaporates over time, more pheromone is left on a shorter path than on a longer path, and thus a shorter path attracts more ants and has a higher pheromone concentration. However, ants do not act deterministically. Not all ants follow the shortest path with the highest pheromone concentration. Instead, some ants occasionally take longer paths or even a wrong route. Therefore, longer and alternative paths are also kept, which brings the robustness feature to the pheromone trails in ACO. When the primary shortest path is obstructed or lost for some reasons (e.g., water flooding), a spare longer path continues to guide ants to the food, collects pheromones, and becomes the new primary path. In the ant colony example, all four basic principles of self-organization appear. First, the shortest path attracts more ants and collects more pheromones, which further attracts more and more ants (positive feedback). However, due to evaporation, no path can collect an infinite amount of pheromones (negative feedback). Pheromones left by an ant on the ground attract other ants and influence their behavior (mutual interactions). Finally, ants occasionally take a longer or wrong path (fluctuations); refer to the illustration below for the above description;
In general, four basic principles can be found in the self-organization of biological systems. Positive feedback, for example, recruitment or reinforcement, permits the system to develop itself and promotes the creation of structure by acting as an amplier for a desired outcome. On the other hand, negative feedback reacts to the influence on the system behavior caused by previous bad adaptations. Furthermore, it contributes to the stability by preventing overshoot control. Another important feature is that biological systems usually do not require a global control unit, but operate entirely distributed and autonomous. Each individual of the system, for example, cells or swarms of insects, acquires, processes and stores its information locally. However, in order that a self-organized structure can be generated, information must be somehow exchanged among the individuals. This is done by mutual interactions in the form of either direct interactions (e.g., visual or chemical communication) or indirect interactions among all individuals by influencing the environment (e.g., diffusion of pheromones in slime mold or ant trails). Such indirect interaction through the environment is called stigmergy, which is one of the key principles in building self-organizing networks without introducing much overhead involved in direct interactions. Finally, another key characteristic that greatly enhances the stability and robustness of the system is that many decisions are not performed in a deterministic and direct way, but system-inherent noise and fluctuations drive the system to enable the discovery of new solutions.

0 Responses to “ Ants and SON (Self Organizing Networks): Getting Ideas of Self-Organization from Ants ”

Post a Comment