Difusão de Informação em
Meio Sem-fio (2)
 Índice exponencial;
 Índice baseado em localização;
 Programação de broadcast de dados por
demanda;
 Sistema de disseminação de dados (DAYS);
Difusão de Informação em
Meio Sem-fio (2)
 Índice exponencial;
 Índice baseado em localização;
 Programação de broadcast de dados por
demanda;
 Sistema de disseminação de dados (DAYS);
Índice Exponencial
 Objetivo:


Reduzir o overhead no gerenciamento dos índices
gerados em relação aos outros esquemas de índice
apresentados;
Possibilitar o trade-off entre tuning time e latency time,
de acordo com as necessidades da aplicação;
Índice Exponencial
Estrutura
 Dados ordenados no canal de broadcast por
uma chave;
 Buckets de tamanho fixo;
Índice Exponencial
Estrutura
[2
(i 1)
,2  1]
i
Índice Exponencial
Busca
t=1
Índice Exponencial
Busca
t=5
Índice Exponencial
Busca
t=6
Índice Exponencial
Vantagens
 A raiz de uma busca é a tabela de índice do
primeiro bucket acessado (Menor latência);
 Bom suporte contra falhas;
 O tuning time é proporcional ao tamanho do
bcast (N) : [log2(N-1)+1];
Índice Exponencial Generalizado
Estrutura
 Generalização do índice de base 2 para um
índice de base R > 1;
 Agrupamento de I buckets em chunks e
existência de uma tabela de índice para cada
chunk;
Índice Exponencial Generalizado
Estrutura
Índice Exponencial Generalizado
Busca
t=1
Índice Exponencial Generalizado
Busca
t=5
Índice Exponencial Generalizado
Busca
t=6
Índice Exponencial Generalizado
Vantagens
 Facilitar o trade-off entre tuning time e
latency time através da manipulação das
variáveis R e I;


Tuning time: o tempo que um cliente fica ativo
para receber o dado requisitado;
Latency time: o tempo total entre uma requisição
ser emitida e respondida;
Difusão de Informação em
Meio Sem-fio (2)
 Índice exponencial;
 Índice baseado em localização;
 Programação de broadcast de dados por
demanda;
 Sistema de disseminação de dados (DAYS);
Índice Baseado em Localização
Motivação
Uma pessoa andando pelo shopping (A2) e
deseja informação sobre os filmes que estão
sendo exibidos mais próximos dele;
Seu dispositivo móvel sintoniza em um canal
de broadcast sobre todos os filmes exibidos
na cidade e começa a coletar informações;
Índice Baseado em Localização
Motivação
 Necessidade de mapeamento entre a
informação disseminada no broadcast e
localização, a nível de índice;
 O esquema de índice exponencial
generalizado não possui informação sobre
localização;
Índice Baseado em Localização
Necessidades
 Função de mapeamento;
 Broadcast baseado em localização;
 Esquema de índice baseado em localização;
Índice Baseado em Localização
Função de mapeamento e Broadcast
 Conjunto de propriedades globais:
Conjunto de informação de conteúdo (IC);
 Hierarquia de localização (HL);

 Intersecção entre IC e HL;
 Broadcast realizado com base na saída dessa
função para todo os dados de IC e HL;
Índice Baseado em Localização
Esquema de índice baseado em localização
 Adaptação do índice exponencial;
 Dois tipos de índice:

Major Index:


Tipos de dados (Entretenimento, Clima, Filme,...);
Minor Index:

Aponta para o dado (localização);
Índice Baseado em Localização
Esquema de índice baseado em localização
Índice Baseado em Localização
Esquema de índice baseado em localização
Índice Baseado em Localização
Esquema de índice baseado em localização
T=1
Índice Baseado em Localização
Esquema de índice baseado em localização
T=5
Índice Baseado em Localização
Esquema de índice baseado em localização
T=8
Difusão de Informação em
Meio Sem-fio (2)
 Índice exponencial;
 Índice baseado em localização;
 Programação de broadcast de dados por
demanda;
 Sistema de disseminação de dados (DAYS);
Programação de broadcast de dados
por demanda
Motivação:
 E se o dono da unidade móvel
vive em uma cidade onde o clima
é extremamente previsível?
Programação de broadcast de
dados por demanda
 Realizar o broadcast de acordo com a
probabilidade de acesso aos dados;
 Feito com base no histórico de consulta dos
usuários;
 Necessária uma implementação híbrida de
broadcast (pull e push);


Pull : Coletar histórico dos usuários;
Push : Melhor performance para grande número de
usuários e requisições;
Programação de broadcast de
dados por demanda
 Algoritmos:



FCFS (First Come First Serve)
MRF (Most Request First)
Entre outros
Programação de broadcast de
dados por demanda
 Limitação dos algoritmos:


Os algoritmos apresentados selecionam os
dados para broadcast a nível de item de dado e
não de transação;
Aplicações normalmente precisam acessar
dados diversos para realizar uma única
transação;
Programação de broadcast de
dados por demanda
Programação de broadcast de
dados por demanda
 Princípios:


Atualizações na base de dados somente podem
ser realizadas entre ciclos de broadcast;
Um peso deve ser atribuído às transações a fim
de definir a ordem que os dados serão colocados
no broadcast;
Programação de broadcast de
dados por demanda
 Servidor:




Gerar uma lista de transações requisitadas em
ordem decrescente de seus pesos;
Selecionar as transações para o ciclo de
broadcast corrente e distribuir seus dados no
broadcast;
Construir o índice e adicionar ele ao broadcast;
Realizar o broadcast e filtrar requisições
realizadas após o início do broadcast;
Programação de broadcast de
dados por demanda
 Cliente:

Caso algum dado da transação requisitada já
tenha passado, deve aguardar até o próximo
ciclo;
Difusão de Informação em
Meio Sem-fio (2)
 Índice exponencial;
 Índice baseado em localização;
 Programação de broadcast de dados por
demanda;
 Sistema de disseminação de dados (DAYS);
DAta in Your Space (DAYS)
 O objetivo dessa pesquisa é desenvolver e validar
arquiteturas e algoritmos necessários para apoiar
uma abordagem ubíqua na disseminação de dados;
 Características:




Suporta sistemas legados (centralizado e distribuído);
Facilita o uso de transações móveis;
Suporta aplicações dependentes de localização;
Permite o acesso a broadcast de dados;
Referências
 Vijay Kumar, “Mobile Data Base System”
 J. Xu, W. C. Lee, and X. Tang, “Exponential Index: A Parameterized
Distributed Indexing Scheme for Data on Air” – 2004
 T. Imielinski, S. Vishwanath, and B. Badrinath, “Energy Efficient
Indexing on Air” – 1994
 http://engr.smu.edu/cse/dbgroup/, Collaborative Research in DAta in
Your Space – 04/2007