ia364 – métodos de pesquisa faculdade de engenharia elétrica e

IA364 – MÉTODOS DE PESQUISA
FACULDADE DE ENGENHARIA ELÉTRICA E COMUPTAÇÃO
UNIVERSIDADE ESTADUAL DE CAMPINAS
ATIVIDADE 05
REVISÃO DE LITERATURA
Felipe Perez de Oliveira Dias - RA 043423
Prof. Dr. Ivan L. M. Ricarte
MARÇO, 2014
1.
Revisão de Literatura
Alocação de recursos em redes é um tema constantemente investigado em áreas de
engenharia. Segundo Hespanha, Naghshtabrizi, e Xu (2007), qualquer comunicação por
rede pode carregar uma quantidade finita de informação por unidade de tempo, ou seja,
em muitas aplicações esta limitação pode ser uma importante restrição na operação de
um sistema. Largura de banda e a sua alocação são exemplos de variáveis que limitam o
desempenho de sistemas em redes.
Visando estratégias e métodos eficientes para alocação de banda em redes, a
utilização de mecanismos de teoria dos jogos, leilões e precificação é um artifício
recorrente na literatura. No estudo de Yaïche, Mazumdar, e Rosenberg (2000),
conceitos de teoria dos jogos, especificamente barganha de Nash, são utilizados para
criação de métodos e estruturas de alocação de banda de maneira dinâmica, a fim de
maximizar a utilização dos recursos da rede. Os autores apresentam o conceito de
controle de taxa (rate control), que se refere à modulação de largura de banda no tempo,
tornando a atribuição de banda para cada nó de uma rede uma variável de controle. Para
isso, os autores utilizaram métodos de precificação de banda e mecanismos de leilão
aplicados a arquiteturas centralizadas e descentralizadas de controle.
A utilização de leilões em redes para divisão de recursos também é tema abordado
por Jia e Caines (2009). Utilizando técnicas de leilões de segundo preço denominados
PSP (progressive second price), também desenhadas sob uma estrutura de jogos, os
autores propõem métodos numéricos para a implementação eficiente de alocação de
recursos em bases de tempo fixas ou variáveis.
Alocação de banda é relevante em estruturas de controle denominadas NCS
(networked control systems). NCS’s são sistemas distribuídos nos quais a comunicação
entre sensores atuadores e controladores ocorre por meio de uma rede compartilhada de
comunicação (Hespanha, Naghshtabrizi, e Xu 2007). NCS’s são utilizados em
aplicações como robótica, sistemas embarcados, eletrônica veicular e sistemas de
potência onde controladores e plantas não estão diretamente interconectados.
2
NCS’s podem ser definidos em diferentes arquiteturas, mas as mais recorrentes são
as chamadas de malha aberta e de malha fechada. No caso de arquiteturas de malha
aberta como abordados no trabalho de Tipsuwan et al. (2009), o conjunto controlador
atuador planta está diretamente conectado, e o sinal de referência é enviado por meio da
rede. Em arquiteturas de malha fechada, como mostrados em trabalhos como Senol,
Leblebicioglu, e Schmidt (2011) e Jungers et al. (2013), o controlador está conectado ao
atuador por meio da rede. Nestes casos, os atrasos de transmissão da rede podem se
tornar fator decisivo para a instabilidade do sistema de controle.
Por motivos apresentados, deficiências adicionais proporcionadas por sistemas em
rede são importantes no estudo de NCS’s. Segundo análise apresentada por Tipsuwan et
al. (2009), atrasos em comunicação dependem de fatores como protocolos de
agendamento e condições de tráfego. A interferência de atrasos em NCS é estudada por
Wang e Wang (2013), com foco em métodos numéricos para a manutenção de
estabilidade do sistema e distribuição ótima dos controladores.
Outra deficiência existente em NCS é a perda de pacotes em redes, que pode ser
causada por colisão de pacotes, alto tráfego e até mesmo deficiência e limitação de
hardware. Esta situação é modelada por Hespanha, Naghshtabrizi, e Xu (2007),
considerando a disponibilidade do canal de transmissão como uma variável aleatória.
Importante também é a maneira de modelar a transmissão dos dados na rede
considerando a amostragem dos sinais e tempo de transmissão. Tal modelagem é
proposta por Bars et al. (2006) considerando redes digitais e intervalos amostrais fixos
com retentores de ordem zero. Sob esta ótica, Hespanha, Naghshtabrizi, e Xu (2007)
propõem que dados velhos ou não-recentes devem ser descartados uma vez que não são
relevantes para o estado atual do sistema controlado.
Alocação de banda aplicada à NCS é o foco do estudo de Tipsuwan et al. (2009). O
autor sugere um método baseado em leilão e precificação para determinação dinâmica
da proporção de banda para cada agente da rede, e o compara com métodos clássicos
que utilizam estrutura de teoria dos jogos. O autor conclui que o método sugerido é
eficiente e pertinente em NCS.
Contudo, são escassos estudos na literatura que utilizem aplicação de abordagens
clássicas de teoria dos jogos a problemas de alocação de banda em NCS’s. A solução da
3
barganha de Nash, abordada por Osborne e Rubinstein (1994), poderia ser a essência de
um algorítimo de alocação de banda em NCS’s. Soluções alternativas da barganha de
Nash, tema do trabalho de Kalai e Smorodinsky (1975), também poderiam ser usadas
com o mesmo propósito.
Outro ponto que pode ser explorado é a construção de modelos utilizando barganha
de Nash na forma axiomática, estudado por Osborne e Rubinstein (1990), e a
modelagem de preferências e funções utilidades usando parâmetros como QoS (quality
of service) e QoC (quality of control). A construção de funções utilidades e preferências
é abordada no trabalho de Rubinstein (2012).
O presente trabalho visa aplicar métodos ainda não explorados em NCS para
alocação de banda e compará-los com os métodos propostos na literatura recente do
tema.
4
2. Bibliografia
Bars, Ruth, Patrizio Colaneri, Carlos E. de Souza, Luc Dugard, Frank Allgöwer, Anatolii
Kleimenov, e Carsten Scherer. 2006. “Theory, Algorithms and Technology in the Design
of Control Systems.” Annual Reviews in Control 30 (1) (January): 19–30.
doi:10.1016/j.arcontrol.2006.01.006.
http://www.sciencedirect.com/science/article/pii/S1367578806000034.
Hespanha, JP, Payam Naghshtabrizi, e Yonggang Xu. 2007. “A Survey of Recent Results in
Networked Control Systems.” PROCEEDINGS-IEEE 95 (1).
ftp://164.41.49.96/Usuarios/Luis/BACKUP_MEST/Networked Control System Thesis/Bibliografia - Completa/Bib - Articles/[Survey]2007__Hespanha-NaghshtabriziXu__Proc-IEEE-TNCS_A Survey of Recent Results in Networked Control Systems.pdf.
Jia, Peng, e Peter E. Caines. 2009. “Auctions on Networks: Efficiency, Consensus, Passivity,
Rates of Convergence.” In Proceedings of the 48h IEEE Conference on Decision and
Control (CDC) Held Jointly with 2009 28th Chinese Control Conference, 8606–8611.
IEEE. doi:10.1109/CDC.2009.5400496.
http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5400496.
Jungers, Marc, Eugênio B. Castelan, Vitor M. Moraes, e Ubirajara F. Moreno. 2013. “A
Dynamic Output Feedback Controller for NCS Based on Delay Estimates.” Automatica 49
(3) (March): 788–792. doi:10.1016/j.automatica.2012.11.047.
http://linkinghub.elsevier.com/retrieve/pii/S0005109812005833.
Kalai, E, e M Smorodinsky. 1975. “Other Solutions to Nash’s Bargaining Problem.”
Econometrica: Journal of the Econometric Society 43 (3): 513–518.
http://www.jstor.org/stable/1914280.
Osborne, Martin J., e Ariel Rubinstein. 1990. Bargaining and Markets. Academic Press.
http://books.google.com/books?id=JaoUAQAAMAAJ&pgis=1.
———. 1994. A Course in Game Theory. MIT Press.
http://books.google.com/books?id=5ntdaYX4LPkC&pgis=1.
Rubinstein, Ariel. 2012. Lecture Notes in Microeconomic Theory: The Economic Agent (Second
Edition) (Google E-Livro). http://books.google.com/books?hl=ptBR&lr=&id=V34RPWeF42sC&pgis=1.
Senol, Sinan, Kemal Leblebicioglu, e Ece G. Schmidt. 2011. “INtERCEDE: An Algorithmic
Approach to Networked Control System Design.” Journal of Network and Computer
Applications 34 (4) (July): 1326–1341. doi:10.1016/j.jnca.2011.03.018.
http://linkinghub.elsevier.com/retrieve/pii/S1084804511000725.
Tipsuwan, Yodyium, Suwatchai Kamonsantiroj, Jirat Srisabye, e Prabhas Chongstitvattana.
2009. “An Auction-Based Dynamic Bandwidth Allocation with Sensitivity in a Wireless
Networked Control System.” Computers & Industrial Engineering 57 (1) (August): 114–
124. doi:10.1016/j.cie.2008.08.018.
http://linkinghub.elsevier.com/retrieve/pii/S0360835208001848.
Wang, Zhuwei, e Xiaodong Wang. 2013. “Optimal Distributed Control for Networked Control
Systems with Delays.”
5
Yaïche, Haïkel, RR Mazumdar, e Catherine Rosenberg. 2000. “A Game Theoretic Framework
for Bandwidth Allocation and Pricing in Broadband Networks.” … Transactions on
Networking ( … 8 (5): 667–678. http://dl.acm.org/citation.cfm?id=355166.
6