AntNet
Algoritmos de formigas aplicados a
encaminhamento de pacotes em redes
Pedro Neves nº 27836
Algoritmos Formiga

Na natureza …
O comportamento de recolha de alimentos de muitas sociedades de
formigas baseia-se na comunicação indirecta mediada por feromonas.

Enquanto caminham, do ninho para as fontes de alimento e vice-versa,
as formigas deixam um rasto químico que forma um trilho de feromonas.

2 / 17
Ant Colony Optimization (ACO)
1.
2.
3.
4.
Os caminhos mais curtos surgem do comportamento colectivo,
através de:

uma escolha local e probabilística de cada formiga sobre para onde se
mover, tendo maior probabilidade os caminhos que tenham mais
feromonas
 uma forma indirecta de comunicação (Estigmergia)

3 / 17
Feromonas e Estigmergia

Quando as formigas deixam um rasto de feromonas:
modificam o modo como as próximas formigas iram percepcionar o
terreno local
 influenciam a escolha do caminho a seguir das próximas formigas

Ao ler/escrever o sinal químico de feromonas de um local as formigas
estão:

a comunicar indirectamente através do ambiente
 a criar um comportamento colectivo

4 / 17
Encaminhamento em Redes
Um algoritmo de encaminhamento está distribuído por toda a rede
 Tem de escolher o melhor caminho para levar os pacotes até ao seu
destino e evitar congestionamentos

A maioria dos algoritmos serve-se de estruturas de dados nos nós
(Routing Tables)

Estas estruturas são ao mesmo tempo bases de dados e modelos
locais do estado global

a informação que guardam e como a actualizam depende do algoritmo
utilizado

5 / 17
Métricas e Objectivos do Encaminhamento

Métricas
 Atraso na distribuição de pacotes (seg):


Velocidade com que os pacotes são enviados (bits / seg):



qualidade do serviço
quantidade do serviço
Recursos da rede utilizados
Objectivos
com muita carga: aumentar a quantidade de pacotes
enviados no mesmo atraso médio
com pouca carga: diminuir o atraso médio de cada pacote
6 / 17
AntNet: Estruturas de dados

Routing Table: Para um qualquer destino d e para cada nó vizinho n
tem a probabilidade Pnd , que representa a “tendência” de escolher o
nó n como parte do caminho até ao destino d.

Local Traffic Statistics: Contém informação sobre a distribuição do
tráfego em toda a rede, tal como o nó o percepciona.
7 / 17
AntNet: Descrição do algoritmo
1. A cada intervalo de tempo t, em cada nó n, é criada uma formiga
(Foward Ant), com um destino pseudo-aleatório (depende dos padrões
de tráfego)
2. O objectivo de cada formiga é:
descobrir um caminho, desde a origem até ao destino
 deixar, em cada nó visitado, informação útil para futuras formigas

3. Cada Foward Ant guarda, na sua memória privada, os nós que visitou
e o tempo que gastou entre cada um deles.
8 / 17
AntNet: Descrição do algoritmo (cont.)
4. O próximo nó é escolhido tendo em conta:



Routing Tables probabilísticas
Heurística local baseadas no estado das ligações desse nó
memória privada dos nós percorridos até então
5. Se for detectado um ciclo, este é eliminado tal como toda a
informação sobre esse sub-caminho
9 / 17
AntNet: Descrição do algoritmo (cont.)
6. Quando chega ao seu destino a Foward Ant cria uma Backward Ant,
transfere a sua memória para a nova formiga e morre.
7. A Backward Ant faz exactamente o mesmo percurso, mas no sentido
inverso, até à origem.
10 / 17
AntNet: Descrição do algoritmo (cont.)
8. Em cada nó que passa a Backward Ant actualiza a Routing Table local
e o Modelo de Tráfego Local usando informação memorizada e local
11 / 17
AntNet: Método de Decisão

A cada nó k, a formiga, com destino d, escolhe o próximo n entre os
nós vizinhos que ainda não percorreu, ou entre todos os vizinhos
calculando a probabilidade P’nd de “tendência” para esse nó
•
Nk {conjunto de
vizinhos de k}
α peso da heurística
local
•

utilizando uma Heurística Local ln que
reflecte o estado actual do nó k
•
qn – nº de bits à espera
de serem enviados de
k para n
12 / 17
AntNet: Regra de actualização das tabelas

Para descobrir o caminho entre K e D, as probabilidades dos arcos
de saída de K são actualizadas através de um valor de reforço R

O nó f, que é o vizinho de K atravessado pela Backward Ant, recebe
um reforço positivo.

Todos os outros vizinhos recebem um reforço negativo.
13 / 17
AntNet: Foward Vs. Backward Ants

As Foward Ants têm a mesma prioridade que os restantes pacotes …

Dessa forma conseguem obter informação sobre:



o tempo global da viagem
o tempo que levou entre os nós percorridos
a velocidade com que os pacotes estão a percorrer a rede


possíveis congestionamentos
As Backward Ants têm prioridade sobre os outros pacotes

propagam a informação, obtida pela Foward Ant, pelos nós visitados
o mais depressa possível
14 / 17
AntNet: Avaliação do caminho descoberto

O caminho descoberto é avaliado de forma:



implícita, através do tempo decorrido entre a descoberta do
caminho e a actualização das Rounting Tables
implícita, através da actualização das Rounting Tables que
descobrir quais os caminhos que mais frequentemente são
descobertos
explícita, através da avaliação do tempo que a formiga gastou em
viagem T


Mas T não pode ser comparado como absoluto pois é dependente do
congestionamento existente na altura
Associamos ao tempo T uma medida de qualidade R
15 / 17
Bibliografia
“AntNet: Distributed Stigmergetic Control for Communications
Networks”


Gianni Di Caro, Marco Dorigo
IRIDIA,
Université Libre de Bruxelles – Bélgica

“Ant Colony Optimization”
 http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html

Acetatos teóricos de VA

Paulo Urbano
16 / 17
Perguntas?
FIM