Um Protocolo de Roteamento Adaptativo a Carga de

Anais do 4º Workshop de Sistemas Distribuídos Autonômicos - WoSiDA 2014
Um Protocolo de Roteamento Adaptativo a Carga de Bateria e a
presença de falhas em Redes Móveis Ad hoc
Bruno de Jesus Santos1, Sérgio Gorender1
1
Laboratório de Sistemas Distribuídos (LASID) – Departamento de Ciência da
Computação (DCC) – Universidade Federal da Bahia (UFBa)
40.170-11 – Av. Adhemar de Barros S/N, Ondina, Salvador – Ba – Brasil
{brunosantos,gorender}@ufba.br
Abstract. Mobile Ad hoc networks (MANET) are composed of mobile nodes which
communicate through wireless network. These nodes make use of different protocols to
manage the process of route discovery. Considering these mobile devices, features related
to mobility, to the use of batteries, and the presence of communication failures are
challenges to be faced. Given these challenges, the authors present a routing protocol to
the automation of such problems, incorporating diverse concepts to your model from the
area of autonomic computation, seeking partial solution of the current challenges in the
area of Mobile Ad Hoc Networks.
Resumo. Redes Móveis Ad hoc (MANETs) são redes compostas por nós móveis que se
comunicam utilizando interface sem fio e fazem uso de diversos protocolos para gerenciar
o processo de descoberta de rotas. Por serem dispositivos móveis, apresentam desafios
relacionados à mobilidade, ao uso de baterias, e à presença de falhas de comunicação.
Frente a esses desafios, os autores propõem um protocolo que visa a automatização de
tais problemas, incorporando ao seu modelo diversos conceitos da área da computação
autonômica, visando a solução parcial dos atuais desafios da área de Redes Móveis Ad
hoc.
1. Introdução
Redes Móveis Ad hoc (MANET) são redes compostas por dispositivos móveis que
utilizam interface de comunicação sem fio, sendo sua arquitetura projetada para proporcionar
conexão em rede. Por ser uma rede formada por dispositivos móveis, possui topologia dinâmica, e
despreza a necessidade de um dispositivo de rede central para conectar outros dispositivos [Bansal
et al, 1999; Sankar et al, 2005]. Nela, todos os dispositivos conectados assumem o papel de
roteadores móveis [Qin and Kunz, 2004], utilizando-se de protocolos de roteamento e de
tecnologias de comunicação (802.11 - Wi-Fi, 802.15 - Bluetooth, ZigBee, Mesh) [Sankar et al,
2005]. Arquiteturas de redes auto-gerenciáveis têm sido desenvolvidas como soluções emergentes
para as redes móveis [Sankar et al, 2005; Baccelli and Perkins, 2012].
Protocolos para Redes Ad Hoc gerenciam arquiteturas de redes dinâmicas [Qin and Kunz,
2004], compostas por conjuntos de nós que possuem comportamentos individuais, caracterizados
pela mobilidade individual e independente de cada nó, pela carga variável da bateria de cada nó, no
processamento de requisições independentes e na potência de sinal da interface de rede de cada nó,
dentre outros aspectos [Baccelli and Perkins, 2012]. A mobilidade dos nós, a ausência de carga na
bateria de um nó, ou uma falha do dispositivo podem gerar falhas na conexão da rede [Baccelli and
Perkins, 2012, Huang et al, 2009].
Apresentamos um protocolo de roteamento para MANETs, capaz de gerenciar de forma
autonômica a formação de rotas, monitorar a presença de falhas de comunicação, e a possibilidade
de falha de um nó devido a queda no nível da carga de sua bateria. A arquitetura de rede proposta
para este protocolo possibilita a construção de rotas em MANETs, priorizando a maior carga de
bateria dos dispositivos da rede. A carga da bateria dos nós na rota é considerada pelo protocolo
como prioritária, em detrimento de uma rota mais curta, para formar rotas que se mantenham
17
Anais do 4º Workshop de Sistemas Distribuídos Autonômicos - WoSiDA 2014
estáveis por maior tempo. Atualmente existem diversos modelos de mobilidade, sendo que o nosso
modelo leva em consideração que os nós podem se movimentam livremente, assumindo uma
velocidade padrão de movimentação para todos os nós.
O restante do artigo foi organizado da seguinte forma: a Seção 2 introduz o conceito de
redes autonômicas e descreve os desafios encontrados na Gerencia de Redes Móveis Ad hoc, a
proposta de uma arquitetura do nosso modelo de protocolo é descrito na Seção 3; e por fim, as
conclusões da nossa pesquisa são apresentadas na Seção 4.
2. Redes Móveis Ad hoc e seus desafios
MANETs apresentam grandes desafios à sua construção e utilização, devido à sua
dinamicidade, caracterizada pela mobilidade dos dispositivos, pela limitada carga da bateria destes
dispositivos, e pela necessidade da rede em se adaptar às constantes mudanças de estado [Bakht,
2010; Misra, 2012].
Topologia Dinâmica e tempo de duração das rotas criadas. A maioria dos protocolos
tradicionais de roteamento em MANETs (AODV, DSR, OLSR, DSDV, TORA), elegem rotas com
base em inundação de mensagens na rede, sofrendo restrições de desempenho para promoção de
novas rotas em tempo hábil [Bakht, 2010]. Alguns protocolos levam em consideração tais
problemas, mas normalmente possuem restrições relacionadas ao modelo de busca por novas rotas
quando uma rota é desfeita [Qin and Kunz, 2004; Sankar et al, 2005].
Consumo de energia dos dispositivos móveis. Dispositivos em MANETs são
dependentes de energia, sofrendo considerável consumo por parte dos processadores, memórias e
interfaces de rede sem fio. Alguns poucos protocolos para MANETs consideram a carga da bateria
na construção de rotas [Baccelli and Perkins, 2012].
O desenvolvimento de mecanismos autonômicos de busca e de recuperação de rotas.
Provê aos nós a possibilidade de elencar rotas secundárias à rota principal. A replicação de rotas
proporciona o compartilhamento de rotas alternativas para todos os dispositivos no processo de
roteamento em rede [Huang et al, 2009; Zeinab et al, 2012 ].
Auto-gestão da rede, tendo a capacidade de percepção das alterações internas e
externas. Os próprios nós da rede tomam decisões com relação à otimização e recuperação de rotas
existentes. A auto-gestão [Zeinab et al, 2012] deve ser obtida a partir do monitoramento dos
dispositivos que compõe a rota [Huang et al, 2009].
3. Um Protocolo de Roteamento adaptativo à carga de bateria e à presença de
falhas de comunicação em Redes Móveis Ad hoc
Assumimos uma rede formada por dispositivos móveis, com a capacidade de comunicação
sem fio. Os nós podem se mover em qualquer direção, entretanto, a movimentação não é constante,
e não ocorre a grandes velocidades. A rede não é confiável, podendo ocorrer perda de pacotes e não
pode ser particionada.
Os dispositivos possuem uma carga limitada em sua bateria, a qual reduz em maior ou
menor velocidade, dependendo, entre outros aspectos, da potência do sinal de comunicação
utilizada. A mobilidade dos nós, que acontece de forma aleatória, pode gerar a desconexão, quando
dispositivos conectados se movimentam para distâncias superiores às do alcance de seus sinais. Esta
desconexão gera a perda de rotas de comunicação, previamente construídas.
3.1 O princípio de funcionamento do protocolo
O protocolo de formação de rotas adaptativo à carga da bateria leva em consideração os
dois atuais modelos de eleição de rotas em Redes Móveis Ad hoc, o reativo e o pró-ativo.
O protocolo estabelece a construção de rotas em duas etapas: primeiro é gerada a Rota
Principal, entre o nó que originou conexão e o nó destino, ilustrado na Figura 1 como Rota principal
(Linha em negrito que conecta o nó origem, e o nó destino, marcados com um círculo). Este
18
Anais do 4º Workshop de Sistemas Distribuídos Autonômicos - WoSiDA 2014
primeiro modelo de busca de rotas é executado sob demanda, de forma similar ao protocolo AODV.
A partir do nó origem é efetuada uma inundação de mensagens na rede (Flooding) até que o nó
destino seja encontrado. A formação da rota levará em consideração o nível de carga de bateria,
selecionando para a rota principal os nós que possuem maior nível de carga de bateria.
Figura 1. Modelo de arquitetura autonômica para Redes MANET
Após a rota principal ser formada, de forma reativa, os nós que fazem parte desta rota
executarão, de tempos em tempos, uma descoberta de rotas locais, formando assim rotas
denominadas como rotas secundárias (Ilustradas na Figura 1). Este procedimento é feito de forma
pró-ativa, de forma similar ao DSR. Essas rotas servirão como base de redirecionamento automático
da conexão principal (Rota Principal) em caso de falhas.
Todos os nós monitoram periodicamente o nível de sua carga de bateria. Se for atingido um
limite mínimo de carga, o nó informará para o nó anterior em todas as rotas em que participar sua
situação. A formação das rotas secundárias segue o mesmo princípio de escolha da Rota Principal,
levando em consideração apenas os dois nós mais próximos aos nós que compõem a rota principal,
e que possuam maior carga de bateria. Este processo se replicará em dois níveis (Ilustrados na
Figura 1 como Nível 1 e Nível 2, sendo o Nível 0 o nível da Rota Principal).
Caberá ao mecanismo de monitoração, o redirecionamento da rota principal para alguma
rota secundária. A arquitetura utiliza o modelo de zonas (Ilustrado na Figura 1 como Zonas 1, 2 e 3)
para permitir que os nós que formarão a Rota Secundária só se conectem com zonas à frente da sua
própria zona. As zonas serão formadas tendo como base o número mínimo de três nós que fazem
parte da rota principal, e a cada novo conjunto de três nós da rota principal uma nova zona é
formada. Atualmente os autores estudam a possibilidade de alteração deste padrão de forma
adptativa a quantidade de nós que compõem a rede.
No caso de o mecanismo de monitoração identificar um nó com o nível da bateria abaixo
do limite mínimo, a rota principal também será reconstruída, da mesma maneira, assumindo o nó
monitorado como estando com falha. Por possuir a característica de mobilidade, de tempos em
tempos o mecanismo deverá analisar a consistência da rota. Na presença de falhas inesperadas, o
mecanismo deverá ser capaz de redirecionar a conexão utilizando o mesmo modelo descrito acima.
4. Implementação e resultados
A Tabela 1 demonstra alguns resultados de simulações executadas através do simulador
OMNET++. O nosso protocolo está sendo referênciado na tabela como EARP. Foram evidênciados
5 cenários para cada protocolo (AODV, DSR e EARP), possuindo características distintas,
levantando resultados que foram comparados, demonstrados abaixo na Tabela 1.
Através de uma análise inicial, fica evidente que os protocolos AODV e DSR conseguem
19
Anais do 4º Workshop de Sistemas Distribuídos Autonômicos - WoSiDA 2014
eleger suas rotas principais com alguns segundos de vantagem frente a nossa proposta. Contudo,
vale ressaltar o tempo de durabilidade (Funcionamento) da rota principal no nosso modelo. Nos 5
cenários evidenciados, o nosso modelo consegue estabilizar por maior tempo o funcionamento da
rota principal até a presença da primeira falha.
5. Conclusões
Redes Ad Hoc autonômicas fazem parte de um campo relativamente novo no estudo das
redes. As redes Ad Hoc são dinâmicas, e por tal caracteristica precisam ser auto-gerenciáveis,
otimizando a criação de rotas, a recuperação ou o redirecionamento de rotas que possam vir a
apresentar falhas. Entre os diversos desafios apresentados por Redes Móveis Ad Hoc Autonômicas,
está o de gerenciar o uso da carga da bateria dos dispositivos móveis, de forma a otimizar a
comunicação.
Protocolos
C1
C1
C1
C2
C2
C2
C3
C3
C3
C4
C4
C4
C5
C5
C5
AODV
DSR
EARP
AODV
DSR
EARP
AODV
DSR
EARP
AODV
DSR
EARP
AODV
DSR
EARP
Tempo de
Simulação
Área do Projeto
240min
240min
240min
240min
240min
240min
240min
240min
240min
240min
240min
240min
240min
240min
240min
80mX20m
80mX20m
80mX20m
60mX20m
60mX20m
60mX20m
50mX20m
50mX20m
50mX20m
40mX30m
40mX30m
40mX30m
20mX20m
20mX20m
20mX20m
Tipo de
Mobilidade e
Quant. nós
Massa – 50
Massa – 50
Massa – 50
Massa – 40
Massa – 40
Massa – 40
Massa – 30
Massa – 30
Massa – 30
Massa – 10
Massa – 10
Massa – 10
Massa – 25
Massa – 25
Massa – 25
Tecnologia
Tempo de formação
rota principal
Uso da rota principal até a 1ª
falha
802.11n
802.11n
802.11n
802.11n
802.11n
802.11n
802.11n
802.11n
802.11n
802.11n
802.11n
802.11n
802.11n
802.11n
802.11n
0.22s
0.18s
0.29s
0.20s
0.17s
0.24s
0.16s
0.11s
0.20s
0.8s
0.6s
0.10s
0.12s
0.10s
0.14s
21min
19min
62min
17min
20min
67min
13min
18min
44min
14min
11min
34min
26min
19min
39min
* C - Cenário
Tabela 1.Resultados das simulações executadas com o simulador OMNET++
Apresentamos neste artigo a ideia de um protocolo para construção e manutenção de rotas
em MANETs, que leva em consideração a carga da bateria dos dispositivos e a possível presença de
falhas de comunicação entre eles. O objetivo é descobrir rotas que possam se manter estáveis por
um tempo maior, possibilitando a comunicação entre os dispositivos móveis, por um maior período
de tempo, com menor probabilidade de ocorrência de falhas.
Referências
Baccelli, e.; Perkins, c. (2012) “Multi-hop Ad Hoc Wireless Communication” IETF: Internet Draft.
p. 11.
Bakht, H (2010) “Survey of Routing Protocols for Mobile Ad-hoc Network” International Journal
of Information and Communication Technology Research, Manchester, v. 1, n. 6, p. 13.
Bansal, M.; Rajput, R.; Gupta, G (1999) “RFC 2501: Mobile Ad hoc Networking (MANET):
Routing Protocol Performance Issuesand Evaluation Considerations”. IETF: RFC Network
Working Group. p. 12.
Huang, Yangcheng; Handurukande, Sidath; Bhatti, Saleem (2009) “Autonomic MANET Routing
Protocols” Journal of Networks, vol. 4, no. 8, Irlanda.
Misra, P (2012). “Routing Protocols for Ad Hoc Mobile Wireless Networks” Washington
University in St.Louis - Department of Computer Science & Engineering, p. 45.
Qin, L.; Kunz, T (2004) “Survey on mobile ad hoc network routing protocols and cross-layer
design” Carleton University: Systems and Computer Engineering, Technical Report SCE-04-14.
p. 26.
Sankar, R.; et al (2005) “Routing and Mobility Management in Wireless Ad Hoc Networks” In:
Mobile computing handbook. 1ª Ed.: CRC Press, v. 1, Cap. 27, p. 659-683.
Zeinab Movahedi, Mouna Ayari, Rami Langar, and Guy Pujolle (2012) “A Survey of Autonomic
Network Architectures and Evaluation Criteria” IEEE Communications Surveys & Tutorials,
Vol. 14, No. 2, Second Quarter
20