Especificação e Análise de um Mecanismo de Controle de Admissão Bidirecional para Protocolos de Roteamento Oportunístico em Redes Ad Hoc sem fio
Aluno: Adriano da Silva Araújo Orientador: Prof. Dr. Leandro Dias da Silva
Dissertacao_Final_Adriano_da_Silva_Araujo_ficha_catalografica_folha_aprovacao.pdf
Documento PDF (2.5MB)
Documento PDF (2.5MB)
Universidade Federal de Alagoas
Programa de Pós-Graduação em Informática - PPGI
Instituto de Computação
Dissertação de Mestrado
Especificação e Análise de um Mecanismo de
Controle de Admissão Bidirecional para
Protocolos de Roteamento Oportunístico em
Redes Ad Hoc sem fio
Mestrando
Adriano da Silva Araújo
Orientador
Prof. Dr. Leandro Dias da Silva
Coorientador
Prof. Dr. Ivo Augusto Andrade Rocha Calado
Maceió, AL
2021
Adriano da Silva Araújo
Orientador
Prof. Dr. Leandro Dias da Silva
Coorientador
Prof. Dr. Ivo Augusto Andrade Rocha Calado
Maceió, AL
2021
Catalogação na fonte
Universidade Federal de Alagoas
Biblioteca Central
Divisão de Tratamento Técnico
Bibliotecária Responsável: Helena Cristina Pimentel do Vale CRB4 - 661
A663e
Araújo, Adriano da Silva.
Especificação e análise de um mecanismo de controle de admissão bidirecional
para protocolos de roteamento oportunístico em redes Ad Hoc sem fio / Adriano da
Silva Araújo. – 2021.
52 f. : il.
Orientador: Leandro Dias da Silva.
Coorientador: Ivo Augusto Andrade Rocha Calado.
Dissertação (Mestrado em Informática) – Universidade Federal de Alagoas.
Instituto de Computação. Programa de Pós-Graduação em Informática, Maceió, 2021.
Bibliografia: f. 40-47.
Apêndices: f. 48-52.
1. Informática. 2. Redes Ad Hoc. 3. Sistemas de comunicação sem fio - Qualidade
de serviços. 4. Sistemas de comunicação sem fio - Controle de admissão. 5. Redes de
computador - Roteamento oportunístico. I. Título.
CDU: 004.7
UNIVERSIDADE FEDERAL DE ALAGOAS/UFAL
Programa de Pós-Graduação em Informática – PPGI
Instituto de Computação/UFAL
Campus A. C. Simões BR 104-Norte Km 14 BL 12 Tabuleiro do Martins
Maceió/AL - Brasil CEP: 57.072-970 | Telefone: (082) 3214-1401
Folha de Aprovação
ADRIANO DA SILVA ARAÚJO
ESPECIFICAÇÃO E ANÁLISE DE UM MECANISMO DE CONTROLE DE ADMISSÃO
BIDIRECIONAL PARA PROTOCOLOS DE ROTEAMENTO OPORTUNÍSTICO EM
REDES AD HOC SEM FIO
Dissertação submetida ao corpo docente do Programa
de Pós-Graduação em Informática da Universidade
Federal de Alagoas e aprovada em 30 de abril de 2021.
Banca Examinadora:
________________________________________
Prof. Dr. LEANDRO DIAS DA SILVA
UFAL – Instituto de Computação
Orientador
__________________________________________
Prof. Dr. IVO AUGUSTO ANDRADE ROCHA CALADO
IFAL– Instituto Federal de Alagoas
Coorientador
________________________________________
Prof. Dr. ALVARO ALVARES DE CARVALHO CESAR SOBRINHO
UFAPE - Universidade Federal do Agreste de Pernambuco
Examinador Interno
________________________________________
Prof. Dr. RAFAEL DE AMORIM SILVA
UFAL – Instituto de Computação
Examinador Interno
________________________________________
Prof. Dr. IVANOVITCH MEDEIROS DANTAS DA SILVA
UFRN- Universidade Federal do Rio Grande do Norte
Examinador Externo
Agradecimentos
Agradeço a Deus.
A minha amada esposa Priscilla e meu amado filho Cristiano Ronaldo por aguentar
minhas angustias e abusos durante boa parte dos últimos 12 meses. Saibam que os amo
muito e sou mais completo com vocês. Sem dúvidas, sou uma pessoa melhor a cada dia
por causa de vocês.
Agradeço aos meus amados pais, Odilon e Marinalva, por toda educação de qualidade
que sempre proporcionaram a mim e a meus irmãos, pois muito de nossas realizações
vocês são responsáveis diretos.
Aos meus irmãos, Osair e Odilon Allisson, agradeço pelo apoio, e ter me dado os
meus sobrinhos maravilhosos, Ana Clara, Sarah, Thor e Megan.
Aos meus orientadores, Leandro Dias e Ivo Augusto, pessoas da minha mais alta
estima e admiração, agradeço por todos os conselhos, pela paciência e por toda a ajuda
nesse período. Espero poder continuar desenvolvendo estudos em conjunto com os
senhores.
A todos os professores do PPGI, por orientações de trabalhos e pelas aulas preciosas.
Aos meus colegas de mestrado, agradeço pelo convívio, pela troca de experiências e
companheirismo durante o Curso.
Ao secretariado do PPGI na pessoa do Anderson Cabral sempre muito preocupado
e atencioso com todos os alunos.
Aos colegas de trabalho, Fernando Carneiro, Marco Albuquerque, Lucas Torquato,
Simplício Neto, João Paulo, Handrik Palmeira, Anderson Maia, Iran Rodrigues e todos
os demais, pela compreensão e apoio em momentos de desânimo.
Por fim e não menos importante, agradeço ao Instituto Federal de Alagoas – IFAL, por
liberar parcialmente este funcionário público do trabalho sem prejuízo dos vencimentos,
pois a realização deste trabalho de pesquisa seria muito mais difícil.
Resumo
Rede Ad Hoc sem fio é um modelo de comunicação que caracteriza-se pela ausência
de um gerenciador central, em que as ligações entre os nós ocorrem de forma independente em relação às demais, ao ponto que, caso uma ligação falhe, as demais não são
impactadas. Neste contexto, uma das abordagens de encaminhamento/roteamento de
pacotes propostas na literatura é o Roteamento Oportunístico (RO). No RO, existe
uma maior probabilidade de entrega dos pacotes, pois todos os caminhos da origem ao
destino são avaliados no roteamento. Tal fato pode ser considerado uma vantagem para
o atendimento dos requisitos de Qualidade de Serviço (Quality of Service - QoS ) das
aplicações. No entanto, prover QoS em ambientes de redes Ad Hoc sem fio oportunistas
não é uma tarefa trivial. Para contribuir com a melhoria deste cenário, o Controle de
Admissão (CA) de fluxos é um mecanismo viável para garantir que novos fluxos só
serão admitidos na rede se houver recursos disponíveis. Este trabalho tem o objetivo de
propor, especificar e analisar um mecanismo de controle de admissão de fluxos de dados
bidirecional em redes Ad Hoc sem fio oportunísticas. Neste sentido, foram utilizados
o OMNeT++, um simulador de eventos discretos de rede, para realizar a avaliação
experimental do mecanismo proposto e uma modelagem formal em Redes de Petri
Coloridas (Colored Petri Nets - CPN ) na ferramenta de software CPN/Tools com o
propósito de aumentar a cobertura de simulação e testes. Com os resultados obtidos foi
possível identificar que para o modelo proposto, um fluxo será admitido somente se,
após a descoberta de rede, existir nos nós encaminhadores recursos disponíveis para a
transmissão e recepção de dados conforme requerido pela aplicação.
Palavras-chave: Redes Ad Hoc; Roteamento Oportunístico; Qualidade de Serviço;
Controle de Admissão.
vi
Abstract
Wireless Ad Hoc Network is a communication model characterized by the absence
of a central manager where the connections between nodes happen independently to the
others. In case a link fails, it will not impact the others. In this context, a packet routing
approach proposed in the literature is Opportunistic Routing (OR). In OR, there is
a greater probability of packet delivery because all paths from source to destination
are evaluated in routing, this fact can be considered an advantage for meeting the
Quality of Service (QoS) requirements of the applications. However, providing QoS in
opportunistic wireless Ad Hoc network environments is not a trivial task. To contribute
to the improvement of this scenario, the Admission Control (AC) of flows is a viable
mechanism to guarantee that new flows will only be admitted into the network if
resources are available. This work aims to propose, specify and analyze an admission
control mechanism for bidirectional data flows in opportunistic wireless Ad Hoc networks.
In this sense, OMNeT++, a discrete network event simulator, was used to perform the
experimental evaluation of the proposed mechanism and a formal model in Colored
Petri Nets (CPN) in the CPN/Tools software tool in order to increase the coverage
simulation and testing. With the results obtained, it was possible to identify that for
the proposed model, a flow will be admitted only if, after the network discovery, there
are resources available in the forwarding nodes for the transmission and reception of
data as required by the application.
Keywords: Wireless Ad Hoc Networks; Opportunistic Routing; Quality of Service;
Admission Control.
vii
Lista de Figuras
1.1
Modelos de rede sem fio. Fonte: [16] . . . . . . . . . . . . . . . . . . . .
2.1
Encaminhamento de pacotes em uma topologia de rede com baixa por-
2
centagem de entrega . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.1
Módulos simples e compostos do OMNeT++. Fonte [56] . . . . . . . .
16
3.2
Tela de simulação do OMNeT++ . . . . . . . . . . . . . . . . . . . . .
17
3.3
Marcação inicial do modelo de CPN para o exemplo de transmissão por
difusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.4
Marcação após o disparo da transição Rede . . . . . . . . . . . . . . . .
20
4.1
Processo de seleção dos trabalhos . . . . . . . . . . . . . . . . . . . . .
23
4.2
Simuladores de rede utilizados nos trabalhos analisados . . . . . . . . .
24
5.1
Exemplo de topologia da rede Ad Hoc sem fio em que nS e nD representam
os nós de origem e destino, respectivamente . . . . . . . . . . . . . . .
5.2
Envio inicial de pacote por difusão nS → nD para descoberta das rotas
de ida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3
5.6
29
Rotas descobertas de nD → nS , representadas pelas setas verdes, após o
finalização do processo de volta . . . . . . . . . . . . . . . . . . . . . .
5.5
28
Rotas descobertas de nS → nD , representadas pelas setas verdes, após o
finalização do processo de ida . . . . . . . . . . . . . . . . . . . . . . .
5.4
28
30
Exemplo de topologia de rede com 5 nós encaminhadores utilizada na
realização do experimento 1 . . . . . . . . . . . . . . . . . . . . . . . .
34
Modelo em CPN proposto para a avaliação do controle de admissão . .
36
viii
A.1 Relatório resumido da simulação da página Phase2 do modelo de CPN
para o ambiente de rede com 5 nós encaminhadores . . . . . . . . . . .
48
A.2 Relatório resumido da simulação da página Phase2 do modelo de CPN
para o ambiente de rede com 8 nós encaminhadores . . . . . . . . . . .
49
A.3 Relatório resumido da simulação da página Phase2 do modelo de CPN
para o ambiente de rede com 10 nós encaminhadores . . . . . . . . . .
50
Lista de Tabelas
2.1
Requisitos de desempenho para serviços baseados em texto, áudio e vídeo
adaptado de [21] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.1
Comparativo entre softwares simuladores de rede. . . . . . . . . . . . .
18
4.1
Bases eletrônicas pesquisadas . . . . . . . . . . . . . . . . . . . . . . .
22
4.2
Critérios de inclusão e exclusão . . . . . . . . . . . . . . . . . . . . . .
22
5.1
Parâmetros de configuração para o ambiente de simulação do OMNeT++ 34
5.2
Tempo de resposta em segundos para a descoberta de rede e reserva de
recursos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
x
35
Sumário
1 Introdução
1
1.1
Descrição do Problema . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2
Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3
Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3.1
Objetivo Geral . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3.2
Objetivos Específicos . . . . . . . . . . . . . . . . . . . . . . . .
5
1.4
Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.5
Estrutura do Documento . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2 Fundamentação Teórica
2.1
2.2
7
Estado da Arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.1.1
Redes Ad Hoc Sem Fio . . . . . . . . . . . . . . . . . . . . . . .
7
2.1.2
Roteamento Oportunístico em Redes Sem Fio . . . . . . . . . .
8
2.1.3
Qualidade de Serviço
. . . . . . . . . . . . . . . . . . . . . . .
11
2.1.4
Controle de Admissão em Redes Sem Fio . . . . . . . . . . . . .
13
Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3 Ferramentas de simulação e análise de rede
15
3.1
Simuladores de Eventos Discretos de Rede . . . . . . . . . . . . . . . .
15
3.2
Redes de Petri Coloridas . . . . . . . . . . . . . . . . . . . . . . . . . .
17
4 Revisão da Literatura Sobre Controle de Admissão Bidirecional
21
4.1
Protocolo da Revisão . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.2
Resultados da Revisão . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
xi
5 Mecanismo de Controle de Admissão Proposto
26
5.1
O Mecanismo de Controle de Admissão Bidirecional . . . . . . . . . . .
26
5.2
Processo de Reserva
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
5.3
Avaliação Experimental do Mecanismo . . . . . . . . . . . . . . . . . .
32
5.3.1
5.3.2
Experimento 1: Simulação do Funcionamento do Mecanismo no
OMNeT++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
Experimento 2: Modelagem em Redes de Petri Coloridas . . . .
35
6 Considerações Finais e Trabalhos Futuros
37
6.1
Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
6.2
Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
A Relatórios das Simulações Realizadas no CPN/Tools
48
B Lista de Abreviaturas e Siglas
51
Capítulo 1
Introdução
As redes de computadores sem fio em seu modelo tradicional são caracterizadas
por dispositivos que estão conectados a uma infraestrutura composta por uma ou mais
estações centrais que desempenham o papel de gerenciar o processo de comunicação entre
os diversos dispositivos a ela conectada. Neste modelo, os dispositivos são fortemente
dependentes, ao ponto que caso falhe um dos componentes centrais da infraestrutura, a
comunicação entre todos os dispositivos conectados a esta rede estará comprometida.
De modo geral, redes de comunicação sem fio apresentam benefícios como: facilidade
de instalação e manutenção [2], flexibilidade [10], escalabilidade [12] e mobilidade [1]
[61]. A facilidade de instalação e manutenção é ressaltada pela não necessidade de
lançamentos de cabeamentos de qualquer natureza, tornando a implantação e expansão
das redes sem fio mais rápida, limpa e econômica. A flexibilidade é caracterizada por
proporcionar um grande número de conexões dentro da área de cobertura do sinal. A
escalabilidade é possibilitada pela simples adição de novos pontos repetidores para a
ampliação do número de dispositivos conectados a rede. E a mobilidade permite que os
dispositivos se desloquem dentro da área de cobertura de sinal sem a perda de conexão.
As redes Ad Hoc sem fio é um modelo de rede que caracteriza-se pela ausência de um
gerenciador central das comunicações. Neste modelo, todos os nós de rede funcionam
como se fossem roteadores que encaminham comunitariamente os pacotes de dados
recebidos com o objetivo de alcançar o destino. Na Figura 1.1 é exibido um modelo de
rede sem fio tradicional, baseado em infraestrutura centralizada, e um modelo de rede
Ad Hoc sem fio.
1
2
(a) Modelo de rede tradicional de infraestrutura
centralizada
(b) Modelo de rede Ad Hoc sem fio
Figura 1.1: Modelos de rede sem fio. Fonte: [16]
Nas redes Ad Hoc sem fio, observam-se as capacidades de auto-organizar e autoconfigurar dinamicamente, sem a perda de conectividade [35]. Contudo, nesse ambiente,
alguns problemas requerem atenção especial, tais como: constante mudança na topologia
da rede, difícil localização dos nós, tratamento de erros de transmissão e recepção de
dados. Devido a essa natureza dinâmica e pelo motivo da comunicação ocorrer na
atmosfera por meio da transmissão de ondas eletromagnéticas é esperado interferências
de toda ordem. Logo, uma quantidade significativa de padrões e protocolos de rede
vem sendo proposta com o objetivo de diminuir a taxa de erros de entrega e otimizar o
roteamento de pacotes.
No que se refere ao roteamento de pacotes, protocolos são padronizações utilizadas
para fornecer um conjunto de funções, como: a) detecção e resposta sobre alterações na
topologia ou serviços de rede; b) construção e gerenciamento de rotas; c) maximização
da capacidade de utilização da rede; e d ) minimização nos atrasos na entrega de pacotes
[27]. Além dessas funções, os protocolos de roteamento podem considerar uma ou várias
rotas para a transmissão de dados da origem ao destino. A vantagem daqueles que
utilizam múltiplas rotas está na possibilidade de fornecer balanceamento de carga e
proteção contra falhas, distribuindo o tráfego entre um conjunto das rotas selecionadas
[25].
O Roteamento Oportunístico (RO) é um tipo de roteamento de pacotes utilizado em
3
redes Ad Hoc sem fio. Nesta abordagem, a principal atividade é selecionar o conjunto
de nós encaminhadores e priorizá-los em relação aos demais [20]. Para isso, o RO realiza
a transmissão por difusão e os nós são dinamicamente escolhidos para encaminhar os
pacotes de dados através de todos os caminhos possíveis desde a origem até o destino.
Qualidade de Serviço (Quality of Service - QoS ) é descrito por Crawley et al. [13]
como um conjunto de requisitos a serem atendidos pela rede para tornar possível a
transmissão de um fluxo de dados. Calado em [9] complementa dizendo que o objetivo
das soluções de QoS é proporcionar a estabilidade da rede por meio da adequação das
necessidades de transmissão das aplicações em face aos recursos de rede disponíveis.
Aplicações da atualidade como Voice over Internet Protocol (VoIP), videoconferência,
jogos interativos, controle de pelotão de veículos (platooning of vehicles), Unmanned
Aerial Vehicles (UAV), telepresença, entre outros, necessitam de suporte de QoS para
funcionar de maneira adequada.
Controle de Admissão (CA) é um mecanismo que gerencia os recursos disponíveis de
rede. Nele os nós, de forma distribuída ou centralizada, determinam se um novo fluxo
pode ser aceito na rede. O seu objetivo é a preservação de QoS dos fluxos já existentes
na rede quando ocorre a chegada de uma nova solicitação, haja visto que novos fluxos
só serão admitidos se houver recursos disponíveis [36]. O CA deve ainda melhorar os
níveis de utilização da rede e ter um custo computacional relativamente baixo capaz
oferecer resposta em tempo real.
Mecanismos de CA propostos na literatura como em Jat et al. [21] afirmam que
a adaptação dinâmica da janela de contenção é uma maneira suficientemente capaz
de melhorar o desempenho de um CA afim de se garantir a máxima utilização da
capacidade de um canal. Siram et al. em [51] levam em consideração o problema de
roteamento e escalonamento de fluxos que apresentam diferentes requisitos de QoS em
redes sem fio de múltiplos saltos. Hosseini et al. em [19] afirmam que o CA é um
mecanismo essencial para gerenciar o tráfego gerado por usuários em redes de sensores
sem fio cognitivas (Cognitive Radio Sensor Networks - CRSNs), e assim atender os
requisitos de QoS solicitados. Hosseini et al. ainda em [19] modelaram um CA por
meio de um processo de semi decisão de Markov [41] com o objetivo de obter a política
ideal para controlar o tráfego de CRSNs e obter a recompensa máxima.
1.1 Descrição do Problema
4
Yuan e Muntean em [64] afirmam que o CA e a equidade de downlink/uplink são
dois problemas críticos para serviços como VoIP em redes do padrão IEEE 802.11 e
propõem uma solução que envolve várias camadas chamada de cross-layer. Nela ocorre
a interação de toda a pilha TCP/IP [52] como forma de otimizar o desempenho geral
da rede, permitindo por exemplo, ao CA localizado na camada de aplicação, explorar
dados ou informações providas na camada de enlace para a tomada de decisão. Calado
em [8] propõe um mecanismo de CA que observa o fluxo na direção do servidor para o
cliente em redes sem-fio oportunísticas, baseando-se em limiares estrito (hard ) e suave
(soft) para garantir respectivamente a QoS entre o mínimo requerido e o ideal. Desse
modo, permite-se a alocação de recursos e transmissão de fluxos de dados multimídia.
1.1
Descrição do Problema
Apesar do RO aumentar a probabilidade de entrega dos pacotes de dados da origem
ao destino, a característica de transmissão por difusão pode ocasionar a inundação de
rede (flooding) e consequentemente consumir todo o recurso disponível. Além disso, o
paradigma de RO apresenta também questões desafiadoras como: a) a coordenação
e seleção dos nós encaminhadores da rede; b) as maneiras de evitar interferências e
retransmissão (duplicação) entre nós vizinhos; e c) as técnicas para priorizar a escolha
dos melhores encaminhadores da origem ao destino. Dessa maneira, faz-se necessário a
adoção de um mecanismo de CA para a coordenação dos nós e o gerenciamento dos
recursos de rede disponíveis.
Este trabalho concentra a pesquisa em redes sem fio de malha (mesh) em que precisase garantir condições de QoS mínimas para realizar uma comunicação bidirecional, ou
seja transmissão e recepção entre origem e destino. Visto que, em redes sem fio o fluxo
de ida pode interferir no fluxo de volta, o controle bidirecional justifica-se para melhorar
a estabilidade da rede.
Após descrever o problema, surge a seguinte questão de pesquisa: Como fornecer
QoS para aplicações em redes Ad Hoc sem fio que necessitem requisitos de largura de
banda para transmissão e recepção de dados?
1.2 Motivação
1.2
5
Motivação
Diante do apresentado, foram realizadas pequisas bibliográficas em que não foi
possível observar trabalhos relacionados recentes sobre mecanismos que realizem CA em
ambientes de RO e que realizem o controle de fluxo em ambos os sentidos. Considerando
uma situação hipotética da comunicação de um nó n1 com um outro ni , o processo de
descoberta e definição de rotas no Ad Hoc On-Demand Distance Vector (AODV) [43],
por exemplo, consiste no envio de pacotes conhecidos como Route Request (RREQ)
por broadcast na rede, iniciando de n1 até alcançar ni . Logo após, ni retorna um
pacote do tipo Route Reply (RREP) pelo caminho inverso da requisição com o objetivo
de confirmar a rota. Entretanto, a comunicação sem fio é inerentemente sujeita a
interferências e o caminho de volta poderá não estar disponível. Dessa forma, o fluxo de
volta tende a interferir na confirmação do fluxo de ida. Esta propriedade somente será
observada em cenário de controle de fluxo bidirecional.
1.3
Objetivos
Nesta seção são apresentados o objetivo geral e os específicos diretamente relacionados
a esta dissertação.
1.3.1
Objetivo Geral
O objetivo geral deste trabalho é propor, especificar e analisar um mecanismo
de controle de admissão para atender requisitos de QoS em redes Ad Hoc sem fio
oportunísticas, tendo em conta os fluxos de dados em ambas as direções.
1.3.2
Objetivos Específicos
Considerando que a meta é alcançar o objetivo geral, os seguintes objetivos específicos
são importantes para a condução deste trabalho:
• definir o modelo conceitual do controle de admissão a ser desenvolvido para
realizar o controle de fluxo como proposto;
1.4 Contribuições
6
• simular em diferentes cenários o funcionamento do controle de admissão proposto;
• verificar a existência de anomalias no modelo conceitual.
1.4
Contribuições
A principal contribuição obtida neste trabalho é um mecanismo que realiza o
controle de admissão de fluxos de dados de forma bidirecional em redes Ad Hoc sem
fio oportunísticas. O mecanismo foi especificado e validado através de simulações em
ferramentas de eventos discretos e de modelagem formal. No primeiro experimento, foi
implementado um modelo para representar o comportamento desejado do mecanismo.
Foi utilizado o simulador de eventos discretos, OMNeT++, em conjunto com o INET,
um framework para redes de computadores. No segundo experimento, um modelo em
Coloured Petri Nets (CPN) foi desenvolvido na ferramenta de software CPN/Tools.
1.5
Estrutura do Documento
O restante do documento está organizado da seguinte maneira:
• o Capítulo 2 apresenta a preparação para a pesquisa por meio de uma fundamentação teórica. São apresentados: os conceitos relacionados ao trabalho; o panorama
sobre o estado da arte;
• o Capítulo 3 apresenta uma breve discussão sobre as ferramentas de simulação e
análise de rede necessárias para a validação do trabalho;
• o Capítulo 4 apresenta uma investigação sobre a questão de pesquisa por meio de
uma revisão da literatura;
• o Capítulo 5 apresenta a especificação do mecanismo de controle de admissão
proposto, bem como a avaliação experimental do seu funcionamento;
• o Capítulo 6 apresenta as considerações finais e direcionamentos para trabalhos
futuros.
Capítulo 2
Fundamentação Teórica
Os aportes teóricos que aqui são apresentados deram suporte à pesquisa realizada e
mostram-se necessários para fundamentar o trabalho.
2.1
Estado da Arte
2.1.1
Redes Ad Hoc Sem Fio
Redes Ad Hoc sem fio são modelos caracterizados pela ausência de controladores
ou centralizadores das comunicações. Além disso, possuem a capacidade de se autoorganizar e auto-configurar dinamicamente, sem interrupção ou perda de conectividade.
Mobile Ad Hoc Networks (MANETs), Wireless Mesh Networks (WMNs), Vehicular
Ad Hoc Networks (VANETs), Wireless Body Area Network (WBAN), Wireless Sensor
Networks (WSN) são alguns destes tipos de rede. Dentre as áreas de aplicação é possível
citar: monitoramento de sinais biomédicos, automação industrial, monitoramento de
eventos sismológicos, veículos inteligentes, entre outros.
Segundo Dandjinou et al. [14], com a popularização da tecnologia, as redes Ad Hoc
sem fio receberam a atenção da comunidade científica em busca de proporcionar melhores
índices de Qualidade de Serviço e de entrega de pacotes. Entretanto, a dificuldade de
localização dos nós, o tratamento de erros de transmissão e recepção de dados são
alguns problemas que requerem atenção especial para construção de uma rede estável.
Em redes Ad Hoc sem fio, o protocolo de roteamento é componente fundamental
7
2.1 Estado da Arte
8
para possibilitar a comunicação entre dois dispositivos distantes. Eles devem realizar
rotinas capazes de mapear a topologia da rede, tornando possível a transmissão de
pacotes desde a origem até o destino. Pode-se classificar os protocolos usados nesse tipo
de rede em reativos, proativos e geográficos.
Protocolos reativos são aqueles que estabelecem rotas da origem para o destino
apenas quando há solicitação de envio de pacotes. Pode-se citar como exemplo o Ad
hoc On-Demand Distance Vector (AODV) que para construir a rota dinamicamente,
inicia-se por meio do nó que origina a requisição com o envio de uma mensagem por
difusão (broadcast) do tipo Route Request (RREQ). Esta mensagem é propagada na
rede até o destino que retorna com uma mensagem Route Reply (RREP) ao tempo que
atualiza as tabelas de roteamento. Caso não encontre caminho disponível entre origem
e destino, será gerada uma mensagem Route Error (RERR).
Nos protocolos proativos, os nós trocam informações de rotas com certa periodicidade,
com isso cada nó mantém e gerencia sua própria tabela de roteamento. O Optimized
Link State Routing (OLSR) é um protocolo proativo bastante conhecido, em que cada
nó seleciona um conjunto de vizinhos denominados Multipoint Relays (MPRs) que são
responsáveis pelo encaminhamento e controle do tráfego de pacotes. No cálculo da rota,
os MPRs são usados para compor a rota de um determinado nó de origem para qualquer
destino na rede [11].
Os protocolos classificados como geográficos consideram métricas de posicionamento
físico para construção de rotas. O algoritmo identifica e considera como candidato
o nó melhor localizado geograficamente para o próximo salto em direção do destino.
Vashist e Jain em [58] informam que redes de drones ou multi-UAV são exemplos
de arranjos que utilizam conceitos de redes Ad Hoc sem fio para transferir pacotes de
forma eficiente. São exemplos de protocolos de roteamento geográficos: o UAV Routing
Protocol (URP) [55] que faz uso de classificador de Bayes; e o DTN-LoRa [5] que
apresenta uma abordagem tolerante a atrasos e interrupções.
2.1.2
Roteamento Oportunístico em Redes Sem Fio
Protocolos que realizam Roteamento Oportunístico (RO), especialmente em redes
Ad Hoc sem fio, têm por função a cada etapa do processo de envio de fluxos de dados
2.1 Estado da Arte
9
selecionar dinamicamente um conjunto de nós candidatos (em vez de um único nó)
desde a origem até o destino [48]. Em outras palavras, a transmissão de um nó é feita
por difusão (broadcast) e essa passa a ser percebida por vários outros nós adjacentes que
por sua vez decidem dinamicamente encaminhar pacotes de dados através de múltiplos
caminhos até o destino. Essa característica produz o aumento da vazão da transmissão
e maior confiabilidade de entrega dos pacotes.
Segundo Zeng et al. [65], o RO busca melhorar a confiabilidade do encaminhamento
de pacotes em redes sem fio com vários saltos, aproveitando a natureza de transmissão
do meio sem fio. Diferentemente do roteamento tradicional, em que apenas o caminho
com maior probabilidade de entrega é o escolhido para a transmissão, no RO todos os
nós podem ser compartilhados durante o processo de roteamento [8].
Invés de considerar o meio compartilhado sem fio uma limitação, o RO aproveita
o processo de transmissão por difusão para escolher dinamicamente os nós que irão
encaminhar os pacotes de dados, aproveitando de todos os caminhos possíveis desde a
origem até o destino. Essas características estimularam sua adoção em ambientes de
redes de comunicação Mesh, MANETs, automação da construção civil e infraestruturas
críticas como: abastecimento de água, distribuição de eletricidade, pontes, ferrovias e
gasodutos/oleodutos [44] [42] [33] [63].
Na Figura 2.1 é exibido o encaminhamento de pacotes em uma topologia de rede
com baixa porcentagem de entrega de pacotes. Considerando que o nó 1 transmita
pacotes para o nó 5, por meio dos nós intermediários 2, 3 e 4, as probabilidades
das transmissões serem bem-sucedidas são de 30%, 40% e 5%, respectivamente. No
RO, uma vez que um dos nós intermediários receba o pacote, não precisará haver
retransmissão. Logo, a probabilidade de recebimento por parte do nó 5 será P =
1 − [(1 − 0, 3) ∗ (1 − 0, 4) ∗ (1 − 0, 05)] = 0, 601 ≈ 60%. Enquanto que no roteamento
tradicional, no melhor dos casos, a cada 10 transmissões um número médio de 04 pacotes
serão recebidos pelo nó 5. Em outras palavras, no cenário de RO, a probabilidade de
sucesso da transmissão de um pacote aumenta de 40% para 60% se comparado com o
roteamento tradicional.
O paradigma de RO apresenta questões desafiadoras como: a) a coordenação e
seleção dos nós encaminhadores da rede; b) as maneiras de evitar interferências e
2.1 Estado da Arte
10
Figura 2.1: Encaminhamento de pacotes em uma topologia de rede com baixa porcentagem de entrega
retransmissão (duplicação) de pacotes entre nós vizinhos; e c) as técnicas para priorizar
a escolha dos melhores encaminhadores da origem ao destino.
Heissenbüttel et al. propuseram o ExOR [18], um típico protocolo de roteamento
proativo como solução para coordenar e selecionar nós. O conjunto de nós encaminhadores é selecionado por meio do envio periódico de pacotes de controle por cada um
dos nós para seus vizinhos. No SOAR [28], o nó de origem inicia a transmissão e o
caminho de roteamento é selecionado ao final da transmissão do pacote real, um típico
comportamento de protocolos reativos.
Sobre questões relacionados a interferências, Rozner et al. propuseram o MCExOR
[47], solução proposta especialmente para ambientes de transmissão multi-canal com o
propósito de prevenir que os canais de transmissão venham se sobrepor uns ao outros,
evitando interferências. O ExOR tenta evitar o aumento da retransmissão, limitando o
número máximo de 10 saltos na expectativa de alcançar o destino. Caso esta condição
seja atingida, a requisição é descartada e o destino é considerado inalcançável.
Ainda relacionado à retransmissão de dados em ambiente de roteamento oportunístico, um mecanismo foi proposto por Calado em [8] para evitar o crescimento
exponencial de retransmissão, funcionando da seguinte maneira: durante o processo de
reserva, ao receber um token de requisição, o nó não efetua a retransmissão imediata,
2.1 Estado da Arte
11
invés disso aguarda por um período de tempo aleatório; e caso o nó venha receber novos
tokens para o mesmo fluxo neste intervalo de tempo, os valores serão somados e uma
única requisição será transmitida.
Para escolher os melhores encaminhadores, Leontiadis e Mascolo em [31]
propuseram o GeOpps, uma solução de roteamento geográfico para VANETs que
permite utilizar rotas sugeridas pelo sistema de navegação veicular para a seleção
dos nós encaminhadores. Ding et al. em [15] propuseram o SIOR que na fase de
seleção emprega uma técnica baseada no triângulo de Reuleaux (triângulo esférico) para
identificar os encaminhadores que estiverem mais próximos. O triângulo de Reuleaux
garante que todos os nós candidatos dentro dele possam se comunicar entre si.
2.1.3
Qualidade de Serviço
Qualidade de Serviço (Quality of Service - QoS ) é descrito como um conjunto de
requisitos a serem atendidos pela rede para tornar possível a transmissão de fluxos de
dados [13]. Um dos principais objetivos da adoção de soluções de QoS é a necessidade
de orquestrar as transmissões das aplicações em face dos recursos de rede disponíveis.
Aplicações aprimoradas modernas como: VoIP, videoconferência, jogos interativos,
controle de pelotão de veículos, UAV, telepresença, entre outros, necessitam de suporte
de QoS para funcionar adequadamente.
A Figura 2.2 exibe o comparativo de uso da largura de banda em redes sem e
com suporte à QoS. Na Figura 2.2(a) é representado o comportamento em redes sem
QoS, em que aplicações com comportamento ganancioso consomem toda a largura
de banda, inviabilizando o tráfego de serviços de maior criticidade. Na Figura 2.2(b),
observa-se o comportamento de redes com QoS habilitado, em que a largura de banda
é administrada de acordo com as exigências das aplicações e com parâmetros de
configuração e administração da rede.
Para Jat et al. em [21], os requisitos de desempenho devem ser muito bem definidos
no que se refere a largura de banda, delay, jitter, taxa de perda de pacotes, além de
outros. A Tabela 2.1 exibe o desempenho requerido para diferentes classes de serviços que
possuem diferentes requisitos de QoS. Como pode ser visto, as aplicações de tempo real
requerem uma maior confiabilidade e são mais sensíveis a atrasos (delay) e ordenamento
12
2.1 Estado da Arte
(a) Largura de banda sem QoS
(b) Largura de banda com QoS
Figura 2.2: Comparativo de uso da largura de banda em redes sem e com suporte QoS1
na entrega (jitter ) dos pacotes.
Tabela 2.1: Requisitos de desempenho para serviços baseados em texto, áudio e vídeo
adaptado de [21]
Classe
Tempo real
Streaming
Melhor esforço
Aplicação
VoIP, videoconferência
Streaming vídeo/áudio
http, e-mailing, ftp
Delay
<150ms
Até 10s
Minutos
Jitter
1 ms
1 ms
NA
Taxa de perda
1% (vídeo), 3% (áudio)
1%
0%
Existem dois métodos principais para habilitar QoS em redes de computadores:
• serviços integrados (Integrated Services - IntServ ) que tem como base a reserva
de recursos. O nó de origem solicita ao nó de destino a alocação de recursos
necessários para possibilitar a transmissão dos dados;
• serviços diferenciados (Differentiated Services - DiffServ ) que implementam QoS
com base na definição de tipos de serviços. Neste método, mecanismos de classificação priorizam as aplicações identificadas com requisitos mais exigentes.
Vale ressaltar que os métodos IntServ e DiffServ não são excludentes entre si. Eles
podem ser projetados para uso em conjunto, de forma a acomodar diferentes requisitos
para diferentes contextos de redes.
Priorização por fluxo e priorização por classes são tipos de abordagens de DiffServ
utilizados para melhorar a aplicação de QoS com base em roteamento. Na priorização
por fluxo é definido um conjunto de requisitos necessários para a transmissão. Tais
requisitos são repassados para todos os roteadores que realizam a devida priorização dos
fluxos. Nas soluções que realizam priorização por classes, os fluxos de dados que trafegam
na rede devem ser organizados em classes com os níveis de prioridades identificados
1
https://www.pcwdld.com/what-is-qos
2.2 Trabalhos Relacionados
13
pela rede. Dessa maneira, não é necessário os nós de rede manter informações sobre o
estado de todos os fluxos que os atravessam.
2.1.4
Controle de Admissão em Redes Sem Fio
Controle de Admissão (CA) é um mecanismo possível de ser empregado no gerenciamento dos recursos disponíveis na rede. Mollaei e Darmani em [36] propõem
que uma implementação de CA tem objetivo de controlar a inclusão de novos fluxos
de dados na rede em cumprimento a condições preestabelecidas, além de promover o
compartilhamento racional dos recursos de rede.
De modo mais abrangente, CA visa determinar quais fluxos poderão entrar na rede
e quais não serão permitidos. Este processo será executado durante a entrada do fluxo
na rede, de maneira que o nó de origem transmitirá quais serão os requisitos de QoS
para o fluxo ou qual classe o fluxo pertence [9]. Dessa forma, pode-se afirmar que a
principal finalidade em se implantar CA é disciplinar a utilização de recursos da rede.
Porém, propor CA em redes sem fio não é uma tarefa trivial. A coleta de informações
sobre os recursos de rede disponíveis e a tomada de decisão, considerando parâmetros de
QoS definidos são tarefas desafiadoras tanto na concepção quanto no desenvolvimento
de uma solução eficiente. Ainda se tratando de CA, deve-se existir uma outra etapa
muito importante, a reserva de recursos, momento em que os recursos disponíveis serão
alocados para os fluxos aceitos (admitidos).
2.2
Trabalhos Relacionados
Nos últimos anos, pesquisadores vêm apresentando soluções relacionadas a CA.
Shang et al. em [49] propuseram um CA para WMNs que aplica modelos matemáticos
da Teoria dos Jogos [60] sobre múltiplos critérios e características para a tomada de
decisão. Jin et al. em [24] apresentaram a proposta de CA para computação em nuvem
móvel com base no processo de decisão de semi-Markov com o objetivo de maximizar o
desempenho e garantir QoS.
Ampririt et al. em [3] apresentaram um mecanismo de CA com base em lógica
Fuzzy para redes definidas por software (Software-Defined Network - SDN ) móveis de
2.2 Trabalhos Relacionados
14
quinta geração (5G) que envolve o controlador SDN, estações rádio base e usuário (User
Equipment - UE ). O CA proposto pelos pesquisadores utiliza os seguintes parâmetros
de entrada: requisitos de QoS; prioridade de rede (slice priority) para o UE; o tempo
de espera de uma solicitação do usuário em um buffer; e o custo de sobrecarga de fatia
de rede.
Caballero et al. em [7] propuseram um framework de fatiamento de rede (networking slicing) para jogos. Os pesquisadores modelaram políticas de CA, juntamente com
um esquema de alocação de recursos e um algoritmo de descarte de usuários (user
dropping), voltados para a manutenção do sistema em Equilíbrio de Nash2 .
Ganesan em [17] propôs um CA que realiza a abordagem baseada em algoritmos
distribuídos, em que cada nó tem o conhecimento dos parâmetros de QoS globais da
rede. Aplicável a redes Ad Hoc sem fio, os pesquisadores apresentaram um modelo de
interferência primária para evitar que dois links quaisquer compartilhem o mesmo nó
no mesmo intervalo de tempo.
Abordagens sobre modelos de CA bidirecional são mais escassas na literatura. Xue et
al. em [62] aplicaram em redes Orthogonal Frequency Division Multiplexing (OFDM) um
modelo de fila de Markov e um método de pesquisa iterativa bidirecional (Bidirectional
Iterative Search - BIS ) para calcular as taxas de aceitação de transferência, e se um novo
fluxo na rede será admitido com base no atraso dos pacotes e no número de fluxos em
andamento na rede. Mehmood et al. em [34] apresentaram um esquema para reduzir
o número de transmissões necessárias para comunicar pacotes bidirecionalmente em
comunicações unicast.
Com base nas pesquisas bibliográficas realizadas, não foi possível localizar trabalhos
relacionados recentes sobre mecanismos que realizem CA de fluxo em ambos os sentidos
para ambientes de roteamento oportunístico.
2
O Equilíbrio de Nash representa a inalterabilidade em uma situação na qual, em um jogo com dois
ou mais jogadores, nenhum jogador tem a ganhar se mudar sua estratégia unilateralmente.
Capítulo 3
Ferramentas de simulação e análise de
rede
Este Capítulo realiza uma breve discussão sobre as ferramentas de simulação e
análise de redes necessárias para a validação do trabalho desenvolvido nesta dissertação.
3.1
Simuladores de Eventos Discretos de Rede
Simuladores de eventos discretos vêm sendo amplamente utilizados tanto para o
projeto quanto para a avaliação do comportamento de implementações de procolos de
comunicação em redes de computadores. Em modelos de eventos discretos, o estado
do sistema muda somente no instante que ocorre um evento. Para todos os demais
instantes de tempo, nada muda no sistema. Em redes de computadores, pode-se admitir
como eventos discretos, por exemplo, o início de uma transmissão de pacotes e o fim de
uma transmissão de pacotes. Isso implica que no intervalo de tempo entre esses dois
eventos, nada de interessante acontece [56].
O OMNeT++ [57], solução adotada nesta dissertação para simulação e análise, é
uma ferramenta composta por módulos que se comunicam trocando mensagens. Esses
módulos são escritos na linguagem de programação C++ e seu funcionamento fazem uso
de bibliotecas de classes de simulação. Outro componente fundamental no OMNeT++
é o Network Description (NED).
NED permite ao usuário declarar módulos simples, os conectar e montar módu15
3.1 Simuladores de Eventos Discretos de Rede
16
los compostos (composição de mais de um módulo simples) conforme ilustrado na
Figura 3.1. No OMNeT++, funcionalidades específicas de protocolos de comunicação
podem ser herdadas de estruturas modelos (templates) e desenvolvidas como projetos
independentes.
Figura 3.1: Módulos simples e compostos do OMNeT++. Fonte [56]
De modo geral, para se construir e executar a simulação de um modelo em OMNeT++, precisa-se ter:
• o código fonte contendo implementações dos módulos (arquivos .cc e .h);
• definições e tipos de mensagens (arquivos .msg) que serão traduzidas em classes
C ++;
• arquivos .ned com a descrição da topologia da rede, a estrutura do módulo com
parâmetros, as portas de comunicações, entre outros; e
• arquivo de configuração (omnetpp.ini) que indica os parâmetros do modelo e
outras configurações.
A interface gráfica de simulação do OMNeT++, exibida na Figura 3.2, tende a
facilitar a depuração, a demonstração ou a execução em lote de simulações. Para
modelar protocolos de comunicação de rede no OMNeT++, um framework bastante
popular é o INET3 . Esse oferece uma série de modelos para redes móveis, com e sem
fio. Protocolos de camada de enlace sem fio (IEE 802.11), protocolos de Internet (TCP,
UDP, IPv4,IPv6), protocolos de roteamento (OSPF, RIP, BGP, etc.) são alguns dos
modelos e componentes facilmente encontrados e disponíveis para uso e modificação.
3
INET Framework. Disponível em: https://inet.omnetpp.org/. Acessado em novembro de 2020.
3.2 Redes de Petri Coloridas
17
Figura 3.2: Tela de simulação do OMNeT++
Outros simuladores de redes podem ser vistos na Tabela 3.1 que exibe um comparativo com o OMNeT++. O SWANS [4] é um simulador para redes Ad Hoc sem fio
que faz uso do Java in Simulation Time - JiST, porém apresenta uma interface gráfica
limitada. O NetSim [54] é um software fim-a-fim, capaz de simular e emular redes em
um ambiente completo de modelagem e desenvolvimento de protocolos de comunicação,
porém é uma ferramenta comercial que representa custos adicionais. O NS-2 [59] é
uma ferramenta muito popular usada para simular redes, porém não tem recebido
atualização (a última ocorreu em 2013) o que limita seu uso em face do surgimento
de novas tecnologias de transmissão. O NS-3 [40], outro simulador de rede de eventos
discretos, suporta pesquisas em redes baseadas em endereçamento IP e não IP, mas não
apresenta interface gráfica de simulação nativa.
3.2
Redes de Petri Coloridas
Redes de Petri Coloridas (Coloured Petri Nets - CPN ),uma variação da tradicional
rede de Petri descrita inicialmente por Murata em [37], é uma linguagem formal que
18
3.2 Redes de Petri Coloridas
Tabela 3.1: Comparativo entre softwares simuladores de rede.
Ferramenta
Linguagem
de programação
Licença de
uso
Interface gráfica
Suporte a rede
sem fio
Atualizado nos
últimos 05 anos
SWANS
Java
NetSim
C / Java /
.NET
ns-2
C++ /
OTcl
ns-3
C++ /
Python
Livre
Comercial
Livre
Livre
Limitada
Sim
Limitada Terceiros
OMNeT++
C++ /
NED
Livre
Acadêmico
Sim
Sim
Sim
Sim
Sim
Sim
Não
Sim
Não
Sim
Sim
possui a capacidade de especificar e validar o comportamento de sistemas complexos [22].
Jensen et al. em [23] relataram CPN como uma linguagem para a modelagem e validação
de sistemas nos quais simultaneidade, comunicação e sincronização desempenham um
papel importante.
Para esta dissertação foi utilizado o CPN/Tools [46], ferramenta que permite modelar
eventos discretos combinando redes de Petri e a linguagem de programação funcional
CPN/ML que é baseada nos padrões Standard ML4 . Apesar de não limitados a esses,
os típicos domínios de aplicação de CPN são os protocolos de comunicação, as redes de
dados, os algoritmos distribuídos e os sistemas embarcados.
A definição formal de uma CPN é descrita em [22] como segue:
• CPN não hierárquica é uma 9-tupla CP N = (P, T, A, Σ, V, C, G, E, I) onde:
1. P é um conjunto finito de Lugares.
2. T é um conjunto finito de Transições tal que P ∩ T = ∅.
3. A é um conjunto finito de Arcos direcionados tal que A ⊆ P × T ∪ T × P .
Significa que um arco pode ligar apenas um lugar a uma transição ou viceversa. Não é possível usar um arco para ligar um lugar a outro lugar ou uma
transição a outra transição.
4. Σ é um conjunto de Cores (tipo de dado) finito e não vazio.
5. V é um conjunto finito de Variáveis tal que T ipo[v] ∈ Σ para todas as
variáveis v ∈ V .
4
Standard ML of New Jersey. Disponível em: http://www.smlnj.org. Acessado em abril de 2021.
3.2 Redes de Petri Coloridas
19
6. C é uma função de Conjunto de cores C : P → Σ que associa cada lugar
a um conjunto de cores.
7. G é a função de Guarda G : T → EXP RV que associa cada transição a
uma guarda tal que T ipo[G(t)] = Bool para todo t ∈ T .
8. E é a função de Expressão de arco E : A → EXP RV que associa cada
arco a a uma expressão tal que T ipo[E(a)] = C(p)M S para todo a ∈ A, onde
p é o lugar conectado ao arco a.
9. I é a função de Inicialização I : P → EXP R∅ que associa a cada lugar
a uma marcação inicial tal que T ipo[I(p)] = C(p)M S para todo p ∈ P .
A simulação da CPN, chamado de jogo das fichas (token game) [32], é guiado pela
ocorrência das transições que, por sua vez, é formalizado pela regra de disparo das
transições. Para uma transição em uma CPN disparar, é preciso habilitá-la satisfazendo
as seguintes regras: a) todos os lugares de entrada de uma transição devem ter fichas
em quantidade maior ou igual que o peso do arco que liga o lugar a transição; e b) a
função de guarda deve ser avaliada para verdadeira. São comportamentos esperados
após o disparo: i ) uma transição habilitada pode ou não ocorrer; e ii ) o disparo de uma
transição habilitada remove fichas dos lugares de entrada e acrescenta nos lugares de
saída, de acordo com os pesos dos respectivos arcos [30].
Figura 3.3: Marcação inicial do modelo de CPN para o exemplo de transmissão por
difusão
Na Figura 3.3 é ilustrado um modelo de CPN para o envio por difusão de um pacote
de dados em uma rede de computadores que possui um transmissor e dois receptores. Na
figura, a marcação (fichas) nos lugares são M(Transmissor) = 1, M(Receptor_1) = 0
e M(Receptor_2) = 0. O peso do arco de Transmissor para Rede é 1. Dessa forma, a
3.2 Redes de Petri Coloridas
20
transição está habilitada. Como não existe função de guarda em Rede, por definição
assumi-se a guarda como verdadeira. O disparo da transição Rede irá remover uma
ficha do lugar Transmissor e depositará uma ficha no lugar Receptor_1, e uma outra
ficha no Receptor_2, como pode ser visto na Figura 3.4.
Figura 3.4: Marcação após o disparo da transição Rede
Capítulo 4
Revisão da Literatura Sobre Controle
de Admissão Bidirecional
Para auxiliar a definição da solução de pesquisa desta dissertação, foram observados
os trabalhos propostos na literatura sobre controle de admissão (CA) para o fornecimento de QoS em redes sem fio. Uma revisão secundária com base nas diretrizes de
Kitchenham et al. em [29] foi conduzida, considerando os trabalhos publicados no
período de janeiro de 2014 a primeira semana de abril de 2021.
4.1
Protocolo da Revisão
O planejamento, a condução e a análise dos trabalhos desta revisão foram realizados
na ferramenta de software Parsifal5 e envolveu as seguintes etapas: (i ) definição das
questões de pesquisa; (ii ) definição da string de busca e bases de pesquisa; (iii ) definição
dos critérios de inclusão e exclusão dos trabalhos; (iv ) extração e classificação de
trabalhos a partir das bases pesquisadas; e (v ) análise e discussão sobre os trabalhos
relacionados.
Uma questão principal de pesquisa (QP) e outras quatro secundárias (QS) orientaram
a revisão. São elas: QP: como está proposto na literatura atual o CA bidirecional para
melhorar a QoS em redes sem fio?; QS01: quais as problemáticas apresentadas para
justificar os trabalhos analisados?; QS02: quais os desafios enfrentados no processo de
5
Parsifal. Disponível em: https://parsif.al/. Acessado em: abril 2021.
21
22
4.2 Resultados da Revisão
desenvolvimento do CA para redes sem fio?; QS03: como foram realizadas a simulação
e a avaliação de desempenho dos trabalhos propostos?; e QS04: quais os benefícios
alcançados ao se implementar o CA nos trabalhos analisados?
As bases eletrônicas e a string de busca utilizada são indicadas na Tabela 4.1.
Tabela 4.1: Bases eletrônicas pesquisadas
Bases Eletrônicas
Engineering Village
IEEE Xplore
Web of Science
Science Direct
Scopus
Springer
String de busca
((“wireless” OR “mobile” OR “wi-fi”) AND
(“quality of service” OR “qos”) AND
(“admission control”) AND
(“end-to-end” OR “bidirectional”))
Os critérios de inclusão e exclusão foram úteis para indicar como serão feitas as
seleções dos trabalhos. Busca-se identificar trabalhos primários, completos, publicados
em língua inglesa que abordem os temas de CA bidirecional para habilitação de QoS
em redes sem fio. Os critérios de inclusão e exclusão são exibidos na Tabela 4.2.
Tabela 4.2: Critérios de inclusão e exclusão
Critérios de Inclusão
Trabalhos sobre CA bidirecional para
habilitação de QoS em redes sem fio
Trabalhos primários
Trabalhos publicados no período de janeiro de 2014 a primeira quinzena de
abril 2021
Trabalhos que respondam à questão de
pesquisa
-
4.2
Critérios de Exclusão
Trabalhos duplicados
Trabalhos resumidos
Trabalhos escritos em língua estrangeira
diferente do inglês
Trabalhos que realizam revisão sistemática ou surveys
Trabalhos que não apresentam discussão
direta sobre o tema
Resultados da Revisão
O processo de seleção dos trabalhos, exibido na Figura 4.1, resultou em 23 trabalhos
aceitos e a análise destes subsidiou as respostas para as questões de pesquisa propostas
na seção 4.1.
4.2 Resultados da Revisão
23
Figura 4.1: Processo de seleção dos trabalhos
A QS01 tem o objetivo de identificar as problemáticas que justificam os trabalhos
realizados. A complexidade da computação e do roteamento em redes Ad Hoc sem fio é
diretamente proporcional ao número de saltos da origem ao destino [51]. Em redes sem
fio, a interferência causada pela transmissão de nós vizinhos é um problema crítico que
afeta seriamente a performance da rede [26].
A QS02 tem o objetivo de identificar os desafios e as complexidades no desenvolvimento do CA em redes sem fio. Observou-se que a incerteza nos caminhos da origem
para o destino [45], a capacidade de prever métricas durante a transmissão [50] e o ajuste
da janela de contenção são os fatores que impactam na eficiência da solução. Janelas
de contenção visam disciplinar transmissões simultâneas provenientes de diferentes nós
na rede. Ao detectar interferências entre si, um mecanismo de back off (intervalo de
tempo aleatório) é ativado, e então cada nó seleciona um tempo aleatório para atrasar
sua própria transmissão [6] [38].
A QS03 tem o objetivo de relacionar as ferramentas de simulação e de avaliação de
desempenho utilizadas nos trabalhos, observando de forma quantitativa a utilização
4.2 Resultados da Revisão
24
de simuladores de rede e métodos formais. Na Figura 4.2 é ilustrado o gráfico com
a predominância de utilização do NS-2 nos trabalhos analisados. Como expressado
anteriormente, o NS-2 é uma ferramenta muito popular e que possui documentação
completa. Porém, devido a não receber atualizações há mais de 05 anos, pode-se gerar
incertezas sobre a simulação de eventos em modelos de redes mais atuais. Sobre métodos
formais, não foi identificado o uso de ferramentas para a especificação, análise e/ou
validação nos trabalhos relacionados a CA em redes Ad Hoc sem fio. A especificação
formal, principalmente nas fases iniciais de desenvolvimento, reduz os erros de requisitos,
pois força-os a uma análise mais detalhada [53].
Figura 4.2: Simuladores de rede utilizados nos trabalhos analisados
A QS04 tem a finalidade de identificar a contribuição gerada pelos trabalhos analisados. A maioria dos autores dos trabalhos selecionados destacam: melhoria de performance
em termos de delay médio [45]; melhoria no gerenciamento de recursos de serviços
bidirecionais (duplex ) em redes sem fio 802.16 [39]; melhoria na taxa de transferência
de dados (throughput) [38]; e melhoria na abordagem de predição de métricas [50]. Em
todos os trabalhos analisados, o objetivo principal é garantir melhores níveis de QoS.
Em resposta a QP (questão principal da pesquisa), observa-se que nos trabalhos
4.2 Resultados da Revisão
25
analisados duas abordagens se destacaram: a) redução ou limitação do número de saltos
da origem ao destino; e b) ajuste dinâmico da janela de contenção para reduzir o
comprimento da fila de transmissão na rede.
Por meio desta revisão da literatura, foi possível perceber um número limitado de
trabalhos sobre CA em ambientes de roteamento oportunístico sem fio. Calado em [8]
já observava para a existência da lacuna de trabalhos sobre CA com foco bidirecional
em redes Ad Hoc sem fio.
Outro ponto de destaque observado, refere-se ao fato de que nenhum dos trabalhos
analisados fez uso de métodos formais para a validação de sua proposta. Portanto,
uma lacuna de pesquisa relevante identificada durante a revisão é destacada: a falta de
análise das abordagens de CA em redes Ad Hoc sem fio utilizando modelos formais.
No próximo capítulo será apresentada a especificação e a avaliação do mecanismo
de CA bidirecional a ser empregado em ambientes de redes sem fio oportunísticas. Este
difere dos demais por apresentar uma abordagem simplificada; por controlar fluxos
bidirecionais com diferentes requisitos de banda para a transmissão e para a recepção;
e por fim, possibilitar a sua utilização em diferentes tipos de aplicação que necessitem
de QoS para o funcionamento.
Capítulo 5
Mecanismo de Controle de Admissão
Proposto
Este capítulo foi dividido em três seções principais: na primeira foi definido o modelo
conceitual do controle de admissão proposto; na segunda detalhou-se o processo de
reserva de recursos; e na terceira foram apresentados os experimentos de simulação
desenvolvidos, um no OMNeT++ com INET framework e outro no CPN/Tools.
5.1
O Mecanismo de Controle de Admissão Bidirecional
Para esta dissertação, assumiu-se uma topologia de rede em que o conjunto de
nós encaminhadores é descrito como N = {ni |i = 1, 2, ..., k − 1, k}. Considerou-se
L = {ni → nj |ni , nj ∈ N } como a representação do conjunto de links entre dois nós do
conjunto N . Isto posto, a Eq. (5.1) definida por Calado em [8, p. 4] indica que um
fluxo pode ser roteado de nS para nD se existe pelo menos um caminho p válido. Logo,
P representa o conjunto dos rotas válidas.
PS→D = {nS → ... → nD |nS , nD ∈ N ∧ ∃
p = (nS → nx , nx → ny , ..., nz → nD )}
(5.1)
O controle de admissão proposto realiza a reserva nos nós utilizando-se de métricas
26
5.1 O Mecanismo de Controle de Admissão Bidirecional
27
externas que são fornecidas ao algoritmo do mecanismo como dado de entrada, e a
maneira como estas são avaliadas não foi o foco deste estudo. É possível nominar
duas das métricas externas utilizadas: (a) a estimativa de banda disponível entre dois
nós; e (b) o conhecimento da coordenada geográfica de qualquer nó da rede. Uma
outra premissa muito importante é a condição de cada nó intermediário ni receber e
processar somente uma requisição por fluxo. Esta característica é extremamente útil
para evitar o inundamento (flooding) da rede ocasionado pelo crescimento exponencial
da retransmissão de pacotes.
No funcionamento do controle de admissão proposto, o nó nS , marcado como origem,
inicia um temporizador e envia pacotes por difusão (broadcast) para se comunicar com o
nó nD , marcado como destino. O pacote enviado possui em um dos campos a indicação
dos requisitos de banda de transmissão e de recepção para o funcionamento da aplicação.
Após o pacote percorrer a rede e alcançar o nó nD , este armazena as mensagens
recebidas por diferentes rotas até que se atinja o requisito de transmissão (ReqT r).
Neste momento, o nó nD inicia a descoberta de rede até o nó nS a fim de verificar se o
requisito de recepção (ReqRe) também será satisfeito. É importante destacar que em
redes sem fio oportunísticas, o caminho PS→D (origem→destino) pode ser diferente
de PD→S (destino→origem). Caso os requisitos de banda de transmissão e recepção
não sejam atendidos o tempo configurado no temporizador é atingido, o controle de
admissão não realiza a reserva e, consequentemente, o fluxo não será admitido na rede.
A Figura 5.1 ilustra o exemplo de topologia da rede Ad Hoc sem fio imediatamente
antes da transmissão do pacote inicial. O nS é aquele que dá origem a solicitação de
reserva à rede e um nó intermediário ni somente encaminhará o pacote se estiver posicionado entre o nó anterior ni−1 e o nó destino nD . Uma vez conhecido o posicionamento
(coordenadas geográficas) de cada nó, pode-se facilmente calcular a distância euclidiana
entre dois pontos por meio da Eq. (5.2).
A distância euclidiana entre dois pontos, A e B, seja A = (xA , yA , zA ) e B =
(xB , yB , zB ) é calculada pela equação:
dAB =
p
(xB − xA )2 + (yB − yA )2 + (zB − zA )2
(5.2)
5.1 O Mecanismo de Controle de Admissão Bidirecional
28
Figura 5.1: Exemplo de topologia da rede Ad Hoc sem fio em que nS e nD representam
os nós de origem e destino, respectivamente
Para realizar a reserva de recursos para a admissão de fluxos de transmissão e de
recepção, respectivamente ReqT r = 50 e ReqRe = 50, inicia-se o envio por difusão de
um pacote a partir de nS com destino a nD , como representado na Figura 5.2. Em
momentos de tempo diferentes, os nós encaminhadores vizinhos recebem o pacote e
verificam se estão no caminho entre nS e nD . Em seguida, cada um consulta a banda
estimada de nS . Havendo banda disponível, os nós encaminham o pacote recebido
ajustando o limite máximo de transmissão do caminho até alcançar o nó de destino nD .
Figura 5.2: Envio inicial de pacote por difusão nS → nD para descoberta das rotas de
ida
5.1 O Mecanismo de Controle de Admissão Bidirecional
29
Na Figura 5.3 são ilustradas duas rotas válidas para o processo de descoberta de ida,
p1 = (nS → n4 → n7 → nd ) e p2 = (nS → n5 → n8 → nd ). Os nós n1 , n2 e n3 descartam
o pacote com a requisição de reserva feita por nS por não estarem na direção do destino
(nD ). A requisição de n9 para nD é descartada pois não existe recurso disponível
para estabelecer link por este caminho. As requisições em n8 e n9 , respectivamente,
recebidas de n4 e n6 são descartadas. Isto ocorre devido a restrição implementada
no mecanismo proposto que permite ao nó intermediário o processamento somente
da primeira requisição de encaminhamento recebida, as demais serão descartadas. O
processo de descoberta de ida é concluído quando há largura de banda disponível para
atender o ReqT r = 50 em nD .
Figura 5.3: Rotas descobertas de nS → nD , representadas pelas setas verdes, após o
finalização do processo de ida
Após a conclusão do processo de descoberta de ida é realizada a descoberta de rede
da volta (nD → nS ) para o atendimento de ReqRe = 50. Na Figura 5.4 é ilustrado os
nós de rede e a largura de banda estimada entre eles. Após alcançar o nó nS e com
o ReqRe atendido, é possível conhecer as rotas de volta p3 = (nD → n7 → n4 → nS )
p4 = (nD → n8 → n5 → nS ) p5 = (nD → n9 → n6 → nS ). Da mesma maneira que
ocorre no processo de ida, as requisições são descartadas quando nós encaminhadores
que não estão no caminho entre nD e nS ou quando recebem mais que uma requisição
para o mesmo fluxo.
5.2 Processo de Reserva
30
Figura 5.4: Rotas descobertas de nD → nS , representadas pelas setas verdes, após o
finalização do processo de volta
5.2
Processo de Reserva
Para realizar o processo de descoberta de rotas na rede e reserva de recursos, o
Algoritmo 1 é proposto. É importante destacar que este algoritmo é executado por cada
nó que receber algum pacote de requisição durante o processo.
O algoritmo supracitado deve receber os seguintes parâmetros de entrada: source,
o nó que origina a requisição; target, o nó de destino; ReqTr, o requisito de banda de
transmissão para a comunicação; ReqRe, o requisito de banda de recepção para a comunicação; listPositionNodes[], a lista com a posição dos nós na rede; e listEstimatedBw[],
a lista com a largura de banda estimada em dois nós vizinhos.
A inicialização do processo de descoberta ocorre na seguinte sequência: a) o nó de
origem executa o método start(); b) o temporizador, timeOut, de 3 segundos é iniciado;
c) o início da primeira volta, phase=1, é definido com o objetivo de descobrir a largura
de banda disponível até o destino, target; e d) o identificador para o fluxo, flowID, é
escolhido. A partir deste momento, o nó de origem dispara por difusão um pacote que é
recebido por seus vizinhos adjacentes.
Na linha 1 do Algoritmo 1 é validada a fase da descoberta de rede. Se a condição
for verdadeira, significa que o requisito de transmissão (ReqT r) será testado para a
descoberta das rotas de ida. Caso a condição seja falsa, o requisito de recepção (ReqRe)
5.2 Processo de Reserva
31
Algoritmo 1 – Processo de Reserva
Input: source, target, ReqT r, ReqRe,
listP ositionN odes[], listEstimatedBw[]
start();
timeOut ← 3s;
currentbw ← 0;
phase ← 1
f lowID ← random(20);
Output: listAvailableBw[] . Lista com larguras de banda entre dois nós vizinhos
1: if (phase = 1) then
2:
reqApp ← ReqT r;
3: else
4:
reqApp ← ReqRe;
5: if (node = target) then
6:
currentbw ← currentbw + estimatedbw ;
7:
if (currentbw >= reqApp) then
8:
if (phase == 1) then
9:
path.push_back(node);
10:
pkt.push_back(path);
11:
phase + +;
12:
target ← source;
13:
pkt.push_back(listAvailableBw);
14:
transmit(pkt);
15:
else
16:
return pkt.listAvailableBw;
17: else
18:
if (isN odeF orwarder(pkt.path_back, node, target)
and !active(F lowID)) then
19:
path.push_back(node);
20:
pkt.push_back(path);
21:
listAvailableBw.push_back(estimatedbw );
22:
pkt.push_back(listAvailableBw);
23:
transmit(pkt);
24:
active.push_back(F lowID);
25:
else
26:
delete pkt
5.3 Avaliação Experimental do Mecanismo
32
será testado para a descoberta das rotas de volta.
Na linha 18, a função isN odeF orwarder (definida no Algoritmo 2) testa se o nó
atual é candidato a encaminhador, utilizando para isto a Eq. 5.2 que realiza o cálculo da
distância entre os nós de rede. Se verdadeira, serão encapsuladas ao pacote informações
úteis para o processo de descoberta, como: o caminho (path); e a largura de banda
estimada entre este atual e o nó anterior (estimatedbw ). Após isso, o nó transmite o
pacote (linha 23) até encontrar o destino (linha 5), momento em que contabilizará os
pacotes recebidos (linha 6) e, logo após atingir o requisito desejado (linha 7), iniciará o
processo de volta (phase = 2).
O Algoritmo 1 finaliza nas seguintes situações: i) o valor do temporizador é atingido
e não há possibilidade de reserva; ii) não existem mais pacotes a serem retransmitidos
na rede; ou iii) o processo de descoberta da rede foi finalizado com o nó de origem
tendo recebido as informações de rota e disponibilidade de recursos da rede. Nesta
última situação, uma lista alimentada em cada iteração, contendo a largura de banda
disponível entre cada dois vizinhos adjacentes é gerada como dado de saída.
Algoritmo 2 – Função auxiliar que identifica se o nó é candidato a encaminhador
1: function isNp
odeF orwarder(P, C, T )
2:
distP T ← (xT − xP )2 + (yT − yP )2 + (zT − zP )2
4:
5:
6:
7:
8:
p
distCT ← p(xT − xC )2 + (yT − yC )2 + (zT − zC )2
distP C ← (xC − xP )2 + (yC − yP )2 + (zC − zP )2
if (distCT ≤ distP T ) and (distP C ≤ distP T ) then
return true
else
return f alse
5.3
Avaliação Experimental do Mecanismo
3:
Neste ponto é descrito como foi realizado o experimento, aplicando os algoritmos
apresentados na seção anterior. Para isto, foram utilizadas as ferramentas de software:
OMNeT++ Discrete Event Simulator ver. 5.6.2 em conjunto com o INET Framework
ver. 4.2.1 na subseção 5.3.1; e CPN/Tools ver. 4.0.1 na subseção 5.3.2. O código fonte
dos experimentos foi disponibilizado no endereço eletrônico https://bit.ly/3tPY2Fn.
5.3 Avaliação Experimental do Mecanismo
33
Para a condução dos experimentos foi utilizado um notebook com sistema operacional
Windows 10, 8GB de memória RAM e processador Intel Core i5-8350U com 1.9Ghz de
frequência.
5.3.1
Experimento 1: Simulação do Funcionamento do Mecanismo no OMNeT++
Objetivos
O presente experimento tem o objetivo de avaliar o processo de consulta a rede para
a reserva de recursos, como também, verificar o tempo decorrido pela consulta em redes
até 10 nós desde a origem até o destino.
Configuração
Para tornar possível a realização do experimento, considerou-se uma rede composta
de nós distribuídos em uma área de 300 m x 200 m conforme a Figura 5.5. Os requisitos
de banda de transmissão e recepção são ReqT r = 50 e ReqRe = 50.
Os nós foram configurados para não apresentarem mobilidade. Em relação aos
parâmetros de transmissão, em cada nó foi ativado uma interface de rede sem fio no
padrão 802.11g com potência de transmissão de 2 mW, sensibilidade de recepção de -85
dBm e taxa máxima de transmissão de 2 Mbps. Também é importante mencionar que a
unidade de medição dos requisitos de transmissão e recepção é conhecida pelos nós da
rede. Para sintetizar as informações, a Tabela 5.1 ilustra os parâmetros de configuração
utilizados no experimento.
Análise dos Resultados
A partir da execução do experimento descrito nesta subseção, coletou-se as informações: i) foi possível encontrar nós encaminhadores e solicitar a reserva de recursos; e ii)
o tempo médio que leva para enviar uma consulta de reserva de recursos da origem ao
destino e receber uma resposta é de 2,744 segundos.
Na Tabela 5.2 é exibido os tempos decorridos para realizar a descoberta de rede
e reserva de recursos. Como pode-se observar, os tempos ficaram muito próximos,
atingindo o melhor resultado com a configuração de 8 nós. Conclui-se que para o
ambiente descrito, a presença de novos nós encaminhadores, ou seja acima de 8 nós,
34
5.3 Avaliação Experimental do Mecanismo
Figura 5.5: Exemplo de topologia de rede com 5 nós encaminhadores utilizada na
realização do experimento 1
Tabela 5.1: Parâmetros de configuração para o ambiente de simulação do OMNeT++
Parâmetro de configuração
Número de simulações
Área de simulação
Número de nós
Modo de operação dos nós da rede
Taxa de transmissão máxima
Tipo de mobilidade
Potência de transmissão
Sensibilidade dos receptores
Nó de origem
Nó de destino
ReqRe
ReqT r
Valor
10
300 m x 200 m
5, 8, 10
802.11 g(mixed)
2 Mbps
Estacionário
2 mW
-85 dBm
host[1]
host[0]
50
50
5.3 Avaliação Experimental do Mecanismo
35
não trará benefícios ao processo de reserva de recursos.
Tabela 5.2: Tempo de resposta em segundos para a descoberta de rede e reserva de
recursos
Quantidade
de nós
05
08
10
5.3.2
Tempo decorrido
para reserva de recursos (s)
2,953
2,617
2,663
Experimento 2: Modelagem em Redes de Petri Coloridas
Objetivos
Este experimento tem o objetivo de validar os valores gerados pelo experimento 1
sobre disponibilidade de banda para cada ligação entre dois nós.
Configuração
O modelo foi desenvolvido em CPN, mais especificamente na ferramenta de software
CPN/Tools ver. 4.0.1. Para condução deste experimento, foi utilizado o mesmo conjunto
de hardware e software descrito no início da seção 5.3. Na Figura 5.6 é ilustrado o
modelo em CPN utilizado neste experimento e o fluxo de execução é o que segue:
• O lugar CTS Down, alimentado manualmente, armazena a sequência de prioridade de transmissão observada em simulação no OMNeT++ na direção
origem→destino.
• O lugar Edges armazena uma lista com todas as ligações entre dois nós envolvidos
no processo de transmissão resultantes da simulação realizada no OMNeT++.
• A transição Resolves Downlink nodes processa a função computeN odesD que
calcula o valor possível de transmissão entre dois nós vizinhos.
• O lugar Group Down armazena em lista o valor processado pela função denominada
computeN odesD.
• O lugar CTS Up armazena a sequência de prioridade de transmissão observada em
simulação do OMNeT++ na direção destino→origem.
5.3 Avaliação Experimental do Mecanismo
36
• A transição Resolves Uplink nodes é habilitada somente quando são concluídas
todas as transições na direção da origem→destino.
• O lugar Group Up armazena em uma lista valores processados pela função
computeN odesU .
• A transição Reserve? quando habilitada processa a função isReserve que retorna
um valor booleano.
• Por fim, o lugar Admitted flow recebe o valor booleano que confirma o resultado
da simulação no OMNet++, caso o fluxo seja admitido (true) ou não (false).
Figura 5.6: Modelo em CPN proposto para a avaliação do controle de admissão
Análise dos Resultados
No Apêndice A são ilustrados os resultados das simulações. Os valores registrados
para os lugares gUp e gDown no passos 11, 17 e 21 das Figuras A.1, A.2 e A.3 no
apêndice supracitado, representam os mesmos valores gerados a partir do experimento 1
descrito na subseção 5.3.1. Por fim, também foi possível observar que o modelo de CPN
é aplicável a configurações de rede com diferentes quantidades de nós encaminhadores.
Capítulo 6
Considerações Finais e Trabalhos
Futuros
Neste capítulo são apresentadas as considerações finais e os trabalhos futuros que
envolveram a pesquisa.
6.1
Considerações Finais
Para que este estudo fosse possível, pesquisas bibliográficas e uma revisão da
literatura sobre abordagens de controle de admissão de fluxos em redes sem fio foram
realizadas. A partir dessas investigações, observou-se lacunas em trabalhos recentes
tanto sobre controle de admissão bidirecional quanto na utilização de métodos formais
para a especificação e análise dos modelos implementados
A análise e validação da proposta foi realizada através de experimentos de simulação
em duas ferramentas diferentes. No primeiro experimento, foi utilizado o simulador
de eventos discretos, OMNeT++, em conjunto com o INET, um framework de redes
de computadores. No segundo experimento um modelo em CPN foi desenvolvido na
ferramenta de sotftware CPN/Tools.
Com os resultados obtidos é possível identificar que determinado fluxo será admitido somente se, após a descoberta de rede, existir nos nós encaminhadores recursos
disponíveis para a transmissão e recepção de dados conforme requerido. Neste sentido,
conclui-se que os objetivos geral e específicos desta dissertação foram atendidos.
37
6.2 Trabalhos Futuros
6.2
38
Trabalhos Futuros
Considerando o trabalho desenvolvido nesta dissertação, pretende-se estender e
aprofundar alguns pontos detalhados a seguir:
• Realizar análises comparativas com outros mecanismos de controle de admissão
disponíveis na literatura. No estágio atual da pesquisa foram realizadas a especificação e a análise de funcionamento do mecanismo proposto. Considera-se muito
importante a comparação deste com outros mecanismos já propostos na literatura.
• Otimizar a alocação de banda. Durante o processo de desenvolvimento foi observado que em determinadas condições, a resposta do mecanismo não realizava a
alocação ótima da banda. Uma dessas situações ocorre quando um nó é fisicamente
capaz de receber pacotes de dois ou mais nós adjacentes. Esta situação poderia
contribuir com o aumento do throughput da rede, mas devido a uma condição de
implementação que tem o objetivo de evitar a inundação de pacotes (flooding)
na rede, cada nó somente processa e encaminha apenas os pacotes de quem ele
primeiro recebeu.
• Expandir a aplicabilidade para cenários diversos. No mecanismo apresentado, foi
considerado um cenário de redes sem fio, sem interferências, sem obstáculos e de
baixa ou inexistente mobilidade. Acredita-se que diversos outros cenários e redes
como VANETs, redes LTE e 5G e redes de sensores podem ser testados. Já em
relação a aplicações, é possível citar chamadas de voz, videoconferência, controle
de pelotão de veículos (platooning of vehicles), automação industrial por meio de
dispositivos de IoT, automação de rede elétrica inteligente (smart grid ), entre
outros.
• Automatizar e incorporar ao modelo o cálculo de novas métricas para a tomada
de decisão. Neste trabalho, algumas métricas foram simplificadas para a validação
conceitual da proposta e outras foram entregues ao mecanismo como dado de
entrada. Um possível trabalho futuro é melhorar a avaliação da tomada de decisão,
incorporando ao mecanismo o cálculo de novas métricas, como por exemplo:
mobilidade (entrada e saída do nó da rede), gasto de energia para encaminhar
6.2 Trabalhos Futuros
39
pacotes, segurança, estimador de largura de banda (vazão) entre nós vizinhos,
divulgação do posicionamento geográfico dos nós da rede e nós com mobilidade e
capacidades de processamento diferentes.
Referências Bibliográficas
[1] Akpanobong, A. C., Othman, M., and Ansa, G. O. Extending throughput
performance for low snr scenarios in wlans using two-level frames aggregation
with enhanced a-msdu. Wireless Personal Communications 115, 2 (Nov 2020),
1695–1710.
[2] Al Raimi, A. M., Chong, C. M., Tang, L. Y., Chua, Y. P., and Al Ajeel,
L. Y. Using mHealth Apps in Health Education of Schoolchildren with Chronic
Disease During COVID-19 Pandemic Era. Springer International Publishing,
Cham, 2021, pp. 305–317.
[3] Ampririt, P., Ohara, S., Qafzezi, E., Ikeda, M., Matsuo, K., and Barolli, L. An integrated fuzzy-based admission control system (ifacs) for 5g wireless
networks: Its implementation and performance evaluation. Internet of Things 13
(2021), 100351.
[4] Barr, R., Haas, Z. J., and van Renesse, R. JiST/SWANS. Disponível em:
http://jist.ece.cornell.edu/, 2004. [Acessado em novembro de 2020].
[5] Baumgärtner, L., Lieser, P., Zobel, J., Bloessl, B., Steinmetz, R., and
Mezini, M. Loragent: A dtn-based location-aware communication system using
lora. In 2020 IEEE Global Humanitarian Technology Conference (GHTC) (2020),
pp. 1–8.
[6] Bhandari, S., and Kaur, P. A novel scheme for optimizing contention window
adjustment in ieee 802.11e wireless networks. In 2016 International Conference on
ICT in Business Industry Government (ICTBIG) (2016), pp. 1–3.
40
REFERÊNCIAS BIBLIOGRÁFICAS
41
[7] Caballero, P., Banchs, A., de Veciana, G., Costa-Pérez, X., and
Azcorra, A. Network slicing for guaranteed rate services: Admission control and
resource allocation games. IEEE Transactions on Wireless Communications 17, 10
(2018), 6419–6432.
[8] Calado, I., Luiz, S. O., Soares, G., Almeida, H., and Perkusich, A.
An admission control mechanism for dynamic QoS-enabled opportunistic routing
protocols. EURASIP Journal on Wireless Communications and Networking 2015,
1 (dec 2015), 224.
[9] Calado, I. A. A. R. Qualidade de Serviço em Redes Mesh Sem Fio Baseada
em Roteamento Oportunístico e Códigos de Rede. Tese (Doutorado em Ciências
no Domínio da Engenharia Elétrica), Universidade Federal de Campina Grande,
Paraíba, 2015.
[10] Chen, X., Ng, D. W. K., Yu, W., Larsson, E. G., Al-Dhahir, N., and
Schober, R. Massive access for 5g and beyond. IEEE Journal on Selected Areas
in Communications 39, 3 (2021), 615–637.
[11] Clausen, T., and Jacquet, P. Optimized Link State Routing Protocol (OLSR).
RFC 3626, RFC Editor, October 2003.
[12] Cooley, T. K. Design, Development, and Implementation of a Wireless Local
Area Network (WLAN): The Hartford Job Corps Academy Case Study. Tese
(Doutorado em Tecnologia da Computação na Educação), Nova Southeastern
University College of Engineering and Computing, 2009.
[13] Crawley, E., Nair, R., Rajagopalan, B., and Sandick., H. A Framework
for QoS-based Routing in the Internet. RFC 2386, RFC Editor, August 1998.
[14] Dandjinou, M. T., Tall, H., and Yélémou, T. Fault-tolerant routing protocol
for ad hoc networks. In 2020 IEEE International Conf on Natural and Engineering
Sciences for Sahel’s Sustainable Development - Impact of Big Data Application on
Society and Environment (IBASE-BF) (2020), pp. 1–6.
REFERÊNCIAS BIBLIOGRÁFICAS
42
[15] Ding, Y.-z., Li, Y.-c., Xu, Y.-c., Zhou, Y.-z., and Zhang, Y.-l. An opportunistic routing protocol for mobile ad hoc networks based on stable ideology.
Wireless Personal Communications 97, 1 (Nov 2017), 309–331.
[16] Dinh Thai, H., Lu, X., Niyato, D., Wang, P., and Han, Z. Applications of
repeated games in wireless networks: A survey. IEEE Communications Surveys &
Tutorials 17 (01 2015).
[17] Ganesan, A. Distributed algorithms for qos in wireless ad hoc networks under
the primary interference model. In 2020 International Conference on Wireless
Communications Signal Processing and Networking (WiSPNET) (2020), pp. 63–66.
[18] Heissenbüttel, M., Braun, T., Bernoulli, T., and Wälchli, M. Blr:
beacon-less routing algorithm for mobile ad hoc networks. Computer Communications 27, 11 (2004), 1076–1086. Applications and Services in Wireless Networks.
[19] Hosseini, E. S., Esmaeelzadeh, V., Berangi, R., and Akan, O. B. Delay
sensitive and power-aware SMDP-based connection admission control mechanism
in cognitive radio sensor networks. Computer Communications 106 (2017), 1–10.
[20] Jadhav, P., and Satao, R. A survey on opportunistic routing protocols for wireless sensor networks. Procedia Computer Science 79 (2016), 603 – 609. Proceedings
of International Conference on Communication, Computing and Virtualization
(ICCCV) 2016.
[21] Jat, D., Shejwal, A., Lusilao, G., and Singh, C. A Review of the Quality
of Service for Time-Sensitive Applications Through Admission Control in 802.11
WLAN. Springer, Singapore, 01 2018, pp. 665–672.
[22] Jensen, K., and Kristensen, L. Coloured Petri Nets: Modelling and Validation
of Concurrent Systems. Springer-Verlag Berlin Heidelberg, 01 2009.
[23] Jensen, K., Kristensen, L. M., and Wells, L. Coloured petri nets and cpn
tools for modelling and validation of concurrent systems. International Journal on
Software Tools for Technology Transfer 9, 3 (Jun 2007), 213–254.
REFERÊNCIAS BIBLIOGRÁFICAS
43
[24] Jin, X., Hua, W., and Wang, Z. Task admission control for application
service operators in mobile cloud computing. EURASIP Journal on Wireless
Communications and Networking 2020, 1 (Oct 2020), 217.
[25] Junhai, L., Danxia, Y., Liu, X., and Mingyu, F. A survey of multicast
routing protocols for mobile ad-hoc networks. IEEE Communications Surveys
Tutorials 11, 1 (First 2009), 78–91.
[26] Kandasamy, S., Marques, C., Calçada, T., Ricardo, M., Matos, R., and
Sargento, S. Call admission control for wireless mesh network based on power
interference modeling using directional antenna. Wireless Networks 22, 7 (2016),
2299–2316.
[27] Karthika K.C. Wireless mesh network: A survey. In 2016 International Conference on Wireless Communications, Signal Processing and Networking (WiSPNET)
(mar 2016), IEEE, pp. 1966–1970.
[28] Katti, S., Katabi, D., Balakrishnan, H., and Medard, M. Symbol-level
network coding for wireless mesh networks. In Proceedings of the ACM SIGCOMM
2008 Conference on Data Communication (New York, NY, USA, 2008), SIGCOMM
’08, Association for Computing Machinery, p. 401–412.
[29] Kitchenham, B., and Charters, S. Guidelines for performing systematic
literature reviews in software engineering. Tech. Rep. EBSE 2007-001, Keele
University and Durham University Joint Report, 2007.
[30] Leandro dias da Silva, Heitor Judiss Savino, Tiago Figueiredo Vieira,
and Davi Bibiano Brito. Modelagem Formal Utilizando Redes de Petri Coloridas
de um Sistema de Automação para abastecimento e Diluição de Ácido Sulfúrico.
In Proceedings XXII Congresso Brasileiro de Automática (2018).
[31] Leontiadis, I., and Mascolo, C. Geopps: Geographical opportunistic routing
for vehicular networks. In 2007 IEEE International Symposium on a World of
Wireless, Mobile and Multimedia Networks (2007), pp. 1–6.
REFERÊNCIAS BIBLIOGRÁFICAS
44
[32] Madougou, S., Varbanescu, A. L., and de Laat, C. Using colored petri
nets for gpgpu performance modeling. In CF ’16: Proceedings of the ACM International Conference on Computing Frontiers (New York, NY, USA, 2016), CF ’16,
Association for Computing Machinery, p. 240–249.
[33] Martín-Campillo, A., Crowcroft, J., Yoneki, E., and Martí, R. Evaluating opportunistic networks in disaster scenarios. Journal of Network and Computer
Applications 36, 2 (2013), 870–880.
[34] Mehmood, T., Libman, L., Dehkordi, H. R., and Jha, S. K. Optimal
opportunistic routing and network coding for bidirectional wireless flows. Computer
Networks 57, 18 (2013), 4030–4046.
[35] Misra, S., Misra, S. C., and Woungang, I., Eds. Guide to Wireless Mesh
Networks. Springer London, 2009.
[36] Mollaei, M., and Darmani, Y. A novel statistical and distributed CAC
algorithm for IEEE 802.11 based single and multi-hop wireless ad hoc networks.
Wireless Networks 24, 3 (2018), 955–967.
[37] Murata, T. Petri nets: Properties, analysis and applications. Proceedings of the
IEEE 77, 4 (April 1989), 541–580.
[38] Namazi, M., Moghim, N., Ghazvini, M., and Askarian, A. Dynamic txop
assignment in ieee802.11e multi-hop wireless networks based on an admission
control method. Wireless Personal Communications 97, 1 (Nov 2017), 749–772.
[39] New, W.-K., Chow, C.-O., and Ma, M. Resource management and qos
provisioning for duplex services in ieee 802.16. Wireless Personal Communications
79, 3 (Dec 2014), 2005–2024.
[40] of Washington NS-3 Consortium, T. U. ns-3 Network Simulator. Disponível
em: https://www.nsnam.org/, 2008. [Acessado em Outubro de 2020].
[41] Pellegrini, J., and Wainer, J. Processos de decisão de markov: um tutorial.
Revista de Informática Teórica e Aplicada 14, 2 (2007), 133–179.
REFERÊNCIAS BIBLIOGRÁFICAS
45
[42] Pentland, A., Fletcher, R., and Hasson, A. Daknet: Rethinking connectivity
in developing nations. Computer 37 (02 2004), 78 – 83.
[43] Perkins, C., Belding-Royer, E., and Das, S. Ad hoc On-Demand Distance
Vector (AODV) Routing. RFC 3561, RFC Editor, July 2003.
[44] Qin, X., and Berry, R. Exploiting multiuser diversity for medium access control
in wireless networks. In IEEE INFOCOM 2003. Twenty-second Annual Joint
Conference of the IEEE Computer and Communications Societies (IEEE Cat.
No.03CH37428) (2003), vol. 2, pp. 1084–1094 vol.2.
[45] Qin, Y., Li, L., Zhong, X., Yang, Y., and Ye, Y. Opportunistic routing
with admission control in wireless ad hoc networks. Computer Communications 55
(2015), 32–40.
[46] Rantzer, A. V. CPN tools for editing, simulating and analysing coloured
Petri nets. In Applications and Theory of Petri Nets 2003: 24th International
Conference, ICATPN 2003 (2003), W. M. P. van der Aalst and E. Best, Eds.,
vol. 2679, pp. 450–462.
[47] Rozner, E., Seshadri, J., Mehta, Y., and Qiu, L. Simple opportunistic
routing protocol for wireless mesh networks. In 2006 2nd IEEE Workshop on
Wireless Mesh Networks (2006), pp. 48–54.
[48] Salehi, M., and Boukerche, A. A novel packet salvaging model to improve
the security of opportunistic routing protocols. Computer Networks 122 (2017),
163–178.
[49] Shang, F., Zhou, D., and He, D. An admission control algorithm based
on matching game and differentiated service in wireless mesh networks. Neural
Computing and Applications 32, 7 (Apr 2020), 2945–2962.
[50] Sharma, V., and Kumar, R. Estimation-based queue scheduling model to
improve qos for end users in manets. Computing and Informatics 35 (01 2016),
1079–1109.
REFERÊNCIAS BIBLIOGRÁFICAS
46
[51] Siram, V., Varma, K., Barman, P., Yellisetty, S., Desiraju, P., Mandal,
S., Vijayan, S. M., Chand, P., Mukherji, U., and Sharma, V. Routing
and Scheduling Transient Flows for QoS in Multi-hop Wireless Networks. 2018
International Conference on Signal Processing and Communications (SPCOM)
(2018), 232–236.
[52] Socolofsky, T., and Kale, C. A TCP/IP Tutorial. RFC 1180, RFC Editor,
January 1991.
[53] Sommerville, I. Software Engineering, 10 ed. Pearson, University of Lancaster,
United Kingdom, University of St Andrews, Scotland, 2016.
[54] TETCOS. NetSim Professional. Disponível em: https://www.tetcos.com/
netsim-pro.html, 2004. [Acessado em novembro de 2020].
[55] Uddin, A., Mansour, A., Le Jeune, D., Ayaz, M., and Aggoune, e.-H. Uavassisted dynamic clustering of wireless sensor networks for crop health monitoring.
Sensors 18 (02 2018), 555.
[56] Varga, A. OMNeT++ Simulator. Disponível em: https://doc.omnetpp.org/
omnetpp/manual/, 2003. [Acessado em Outubro de 2020].
[57] Varga, A., and Hornig, R. An overview of the omnet++ simulation environment. In Proceedings of the 1st International Conference on Simulation Tools
and Techniques for Communications, Networks and Systems & Workshops (ICST,
Brussels, Belgium, Belgium, 2008), Simutools ’08, ICST (Institute for Computer
Sciences, Social-Informatics and Telecommunications Engineering), pp. 60:1–60:10.
[58] Vashist, S., and Jain, S. Location-aware network of drones for consumer
applications: Supporting efficient management between multiple drones. IEEE
Consumer Electronics Magazine 8, 3 (2019), 68–73.
[59] VINT, V. I. T. The Network Simulator - ns-2. Disponível em: https://www.isi.
edu/nsnam/ns/, 1995. [Acessado em novembro de 2020].
[60] von Neumann, J., and Morgenstern, O. Theory of games and economic
behavior. Princeton University Press, 1947.
REFERÊNCIAS BIBLIOGRÁFICAS
47
[61] Xu, M., Yang, Q., Kwak, K. S., and Park, D. Impact of mobility on energy
consumption in wireless networks. Wireless Networks 25, 5 (Jul 2019), 2249–2258.
[62] Xue, C., Xu, W., He, Z., and Niu, K. A distributed call admission control
scheme for qos provisioning in ofdma system. In 2011 IEEE Consumer Communications and Networking Conference (CCNC) (2011), pp. 648–652.
[63] Yoon, S., Jang, S., Kim, Y., and Bahk, S. Opportunistic routing for smart
grid with power line communication access networks. IEEE Transactions on Smart
Grid 5, 1 (2014), 303–311.
[64] Yuan, Z., and Muntean, G. M. IVoIP: An intelligent bandwidth management
scheme for VoIP in WLANs. Wireless Networks 20, 3 (2014), 457–473.
[65] Zeng, K., Lou, W., and Li, M. Multihop Wireless Networks: Opportunistic
Routing, 1st ed. John Wiley & Sons, Ltd, 2011.
Apêndice A
Relatórios das Simulações Realizadas
no CPN/Tools
Figura A.1: Relatório resumido da simulação da página Phase2 do modelo de CPN para
o ambiente de rede com 5 nós encaminhadores
48
49
Figura A.2: Relatório resumido da simulação da página Phase2 do modelo de CPN para
o ambiente de rede com 8 nós encaminhadores
50
Figura A.3: Relatório resumido da simulação da página Phase2 do modelo de CPN para
o ambiente de rede com 10 nós encaminhadores
Apêndice B
Lista de Abreviaturas e Siglas
5G Rede Móvel de Quinta Geração.
AODV
Ad-hoc On Demand Distance Vector
BGP Border Gateway Protocol
CA
Controle de Admissão
CPN
Coloured Petri Nets
CRSN
Cognitive Radio Sensor Networks
CTS
Concurrent Transmission Set
DSDV
Destination-Sequenced Distance Vector Routing
DVR
Distance Vector Routing
ExOR
Extremely Opportunistic Routing
GeOpps
Geographical Opportunistic Routing
GPSR
Greedy Perimeter Stateless Routing
IEEE
Institute of Electrical and Electronics Engineers
IoT
Internet of Things
IPv4
Internet Protocol ver. 4
51
52
IPV6
Internet Protocol ver. 6
LSR
Link State Routing
LTE
Long Term Evolution
MANET
Mobile Ad hoc Network
MCExOR
Multi-Channel Extremely Opportunistic Routing
OFDM
Orthogonal Frequency Division Multiplexing
OLSR
Optimized Link State Routing Protocol
OSPF
Open Shortest Path First
QoS
Quality of Service
RERR
Route Error
RIP
Routing Information Protocol
RO
Roteamento Oportunístico
RREP
Route Reply
RREQ
Route Request
SDN
Software Defined Networking
SOAR
Simple Opportunistic Adaptive Routing
TCP/IP
UAV
Unmanned Aerial Vehicle
VANET
VoIP
Transmission Control Protocol / Internet Protocol
Vehicle Ad hoc Networks
Voice over Internet Protocol
WBAN
Wireless Body Area Networks
WMN
Wireless Mesh Network
WSN
Wireless Sensor Network