Orientador: Lee Luan Ling / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-20T02:24:35Z (GMT). No. of bitstreams: 1 YakovNae_M.pdf: 7990917 bytes, checksum: 122c511d9ba839a2f1464fbe7fca09b4 (MD5) Previous issue date: 2011 / Resumo: Gerência de armazenamento em Redes de Sensores Sem Fio (RSSF) é uma questão muito crítica. Além da RSSFs conter uma vasta quantidade de armazenamento agregada, ela não pode ser usada inteiramente. Portanto, o sistema inteiro falha quando o primeiro sensor tem sua capacidade de armazenamento esgotada, deixando uma grande capacidade de armazenamento inutilizada. Sugere-se que os sensores devem-se ser capazes de detectar as capacidades de armazenamentos inutilizadas, para prolongar as suas funcionalidades. Entretanto, em RSSF de larga escala isso pode ser muito difícil uma vez que os sensores podem não ter conhecimento da existência dos outros. Neste trabalho apresenta-se duas principais contribuições: otimização da capacidade total de armazenamento para RSSF em grande escala e uma nova abordagem de roteamento - Deterministic "Random" Walk (Passeio "Aleatório" Determinístico). Apresenta-se um novo modelo de armazenamento via construção "sob demanda" de Cadeias de Armazenamento Distribuídas ( Distributed Storage Chains (DSC). Estas cadeias representam parcerias entrem os sensores que podem compartilhar suas capacidades de armazenamento. Resultando, os sensores não estão sujeitos às suas limitações de armazenamento, mas para à capacidade total de armazenamento disponível no sistema. Constrói-se estas cadeia via passeio determinístico sobre a topologia sugerida. Todavia, mostra-se que estes passeios apresentam um comportamento aleatório que é muito eficiente em termos de localização de capacidade de armazenamento disponível / Abstract: Storage management of Wireless Sensor Networks (WSN) is a very critical issue in terms of system's lifetime. While WSNs host a vast storage capacity on the aggregate, that capacity cannot be used entirely. Eventually, the entire network may fail when the first sensor has its own storage capacity depleted, leaving behind a large amount of unutilized storage capacity. We suggest that sensors should be able to detect unutilized storage capacity in order to prolong their functionality. However, for large scale WSNs this can be a difficult task, since sensors may not be aware of the existence of others. This work has two main contributions: an optimization of the overall storage capacity for large scale WSNs and a novel routing approach of deterministic "random" walk. We present a new storage model by building "on - demand" Distributed Storage Chains (DSC). These chains represent partnership between sensors that share their storage capacity. As a result, sensors are no longer subjected to their own storage limitations but to the total amount of available storage in the WSN. We construct these chains via deterministic walks over our suggested topology. However, we show that these walks resemble the behavior of random walks and are therefore highly efficient in terms of locating available storage / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

A caracterização de redes e o estudo de sistemas, ambos utilizando grafos, é algo muito usado por várias áreas científicas. Uma das linhas deste estudo é denominada de grafos aleatórios, que por sua vez auxilia na criação de modelos para análise de redes reais. Consideramos um modelo de grafo aleatório não homogêneo criado por Kang, Pachón e Rodríguez (2016), cuja construção é feita a partir da realização do grafo binomial G(n; p). Para este modelo, estudamos argumentos e métodos usados para encontrar resultados sobre o limiar de conectividade, importante propriedade relacionada a existência assintótica de vértices e componentes isolados. Em seguida, constatamos algumas características positivas e negativas a respeito da utilização do grafo para modelar redes reais complexas, onde usamos de simulações computacionais e medidas topológicas. / The characterization of networks and the study of systems, both using graphs, is very used by several scientific areas. One of the lines of this study is called random graphs, which in turn assists in creating models for the analysis of real networks. We consider an inhomogeneous random graph model created by Kang, Pachón e Rodríguez (2016), where its construction is made from the realization of the binomial graph G(n; p). For this model, we studied the arguments and methods used to find results on the connectivity threshold, important property related to asymptotic existence of vertices and isolated components. Then we found some positive and negative characteristics about the use of the graph to model complex real networks, using computer simulations and topological measures.

Estudamos o comportamento da familia aresta-triangulo de grafos aleatorios exponenciais (ERG) usando metodos de Monte Carlo baseados em Cadeias de Markov. Comparamos contagens de subgrafos e correlacoes entre arestas de ergs as de Grafos Aleatorios Binomiais (BRG, tambem chamados de Erdos-Renyi). E um resultado teorico conhecido que para algumas parametrizacoes os limites das contagens de subgrafos de ERGs convergem para os de BRGs, assintoticamente no numero de vertices [BBS11, CD11]. Observamos esse fenomeno em grafos com poucos (20) vertices em nossas simulacoes. / We study the behavior of the edge-triangle family of exponential random graphs (ERG) using the Markov Chain Monte Carlo method. We compare ERG subgraph counts and edge correlations to those of the classic Binomial Random Graph (BRG, also called Erdos-Renyi model). It is a known theoretical result that for some parameterizations the limit ERG subgraph counts converge to those of BRGs, as the number of vertices grows [BBS11, CD11]. We observe this phenomenon on graphs with few (20) vertices in our simulations.

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. / In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.

Em Lora e Singer (Statistics in Medicine, 2008), propusemos um modelo Beta- Binomial/Poisson p-variado para análise dos dados provenientes de um estudo que consistiu em contar o número de tentativas e acertos de um exercício manual com duração de um minuto realizado por doentes de Parkinson, antes e depois de um treinamento. O objetivo era verificar se o treinamento aumentava o número de tentativas e a porcentagem de acerto, o que destaca o aspecto bivariado do problema. Esse modelo leva tais características em consideração, usa uma distribuição adequada para dados de contagem e ainda acomoda a sobredispersão presente na contagem dos acertos. Como generalização, inicialmente, propomos um modelo Beta-Binomial/Poisson-Gama que acomoda sobredispersão também para as contagens dos totais de tentativas, além incluir covariâncias possivelmente diferentes entre as contagens em diversos instantes de avaliação. Neste novo modelo, introduzimos um parâmetro que relaciona o total de tentativas com a probabilidade de acerto, tornando-o ainda mais geral. Obtemos estimadores de máxima verossimilhança dos parâmetros utilizando um algoritmo de Newton-Raphson. Consideramos um outro conjunto de dados provenientes do mesmo estudo para ilustração da metodologia proposta. / In Lora and Singer (Statistics in Medicine, 2008), we proposed a Beta-Binomial/Poisson p-variate model to analyze data from a study which consists in counting the number of trials and successes of a manual exercise in one minute periods, done by Parkinsons disease patients, before and after a training. The purpose was to verify if the training improves the number of trials and the percentage of success, which emphasizes the bivariate aspect of the problem. This model considers these characteristics, uses an adequate distribution to count data and settles the overdispersion suggested in the number os successes. As a generalization, initially, we propose a Beta-Binomial/Poisson-Gama model which also settles the overdispersion suggested by the total number of trials, besides includes possible different covariances between total trial counts in different evaluation instants. In this new model, we introduce a parameter that links the total trials with the success probability, making it even more general. We obtain maximum likelihood estimators for the parameters using an Newton-Raphson algorithm. We consider another data from the same study to illustrate the proposal methodology.

Estudamos o problema de famílias intersectantes extremais em um subconjunto aleatório da família dos subconjuntos com exatamente k elementos de um conjunto dado. Obtivemos uma descrição quase completa da evolução do tamanho de tais famílias. Versões semelhantes do problema foram estudadas por Balogh, Bohman e Mubayi em 2009, e por Hamm e Kahn, e Balogh, Das, Delcourt, Liu e Sharifzadeh de maneira concorrente a este trabalho. / We studied the problem of maximal intersecting families in a random subset of the family of subsets with exactly k elements from a given set. We obtained a nearly complete description of the evolution of the size of such families. Similar versions of this problem have been studied by Balogh, Bohman and Mubayi in 2009, and by Hamm and Kahn, and Balogh, Das, Delcourt, Liu and Sharifzadeh concurrently with this work.

A especificação de funções de covariância espaço-temporais é uma das possíveis estratégias para modelagem de processos dos quais observações são tomadas em diferentes posições do espaço e do tempo. Tais funções podem definir processos separáveis ou não separáveis e na sua especificação deve-se garantir que são funções de covariância válidas atendendo a condição de serem positiva definidas. Entre estratégias para obtenção de tais funções estão as de Cressie e Huang (1999) e Gneiting (2002). A primeira se baseia na idéia de obter funções em um espaç de dimensão aumentada a partir de funções válidas no espaço original e necessita de operações no domínio da freqüência. Alternativamente a segunda proposta utiliza combinação de funções completamente monótonas e estritamente crescentes, evitando inversão de representações espectrais. Há ainda poucos relatos de uso e avaliações comparativas das diferentes propostas. Neste trabalho considerou-se a metodologia proposta por Gneiting, com diferentes valores do parâmetro que indica a força da interação entre o espaço e o tempo. Diferentes modelos foram aplicados à dois conjuntos de dados, um referente a estoques de peixe na costa de Portugual, e outro referente à armazenagem de água em um solo com citros. Utilizou-se a implementação no pacote RandomFields do programa R, revisando-se a metodologia e investigando-se a implementação computacional. Para os dois conjuntos de dados o modelo de covariância separável se mostrou adequado para descrever o comportamento das observações disponíveis sendo a escolha do modelo determinada por ajustes de máxima verossimilhança. / The specification of space-time covariance functions is one of the possible strategies to model processes observed at different locations and time points. Such functions can define separable and non-separable processes and must attend the condition of positivedefiniteness. Among the strategies to obtain such valid functions are the ones suggested by Cressie and Huang (1999) and by Gneiting (2002). The former is based on the idea of obtaining valid functions in a space of increased dimension from valid functions on the primary dimension and requires operations in the frequency domain. Alternatively, the latter combines increasing monotone functions avoiding the inversion of spectral representations. There are still few reports of usage and comparisons of the strategies. This work follows Gneiting?s proposals with different values for the space-time interaction parameter. Models were applied for the analysis of two real data sets, one about fish stocks in the Portuguese coast and a second on soil water storage. The implementation on the R package RandomFields was used, with methodology and computational implementation being reviewed. For both case the separable model provided a satisfactory fit, based on maximum likelihood estimation.

Estudamos sistemas de passeios aleatórios sobre os vértices de um grafo completo. Inicialmente há uma partícula em cada vértice do grafo das quais somente uma está ativa, as outras estão inativas. A partícula ativa realiza um passeio aleatório simples a tempo discreto com tempo de vida que depende do passado do processo, movendo-se ao longo de elos. Quando uma partícula ativa encontra uma inativa, esta se ativa; quando salta sobre um vértice já visitado, morre. O objetivo desta dissertação é estudar a cobertura do grafo completo, ou seja, a proporção de vértices visitados ao fim do processo, quando o número $n$ de vértices tende ao infinito. Analisamos as equações de campo médio para o processo descrito acima, comparando os seus resultados com os do modelo aleatório. Aqui, os resultados do campo médio parecem reproduzir os do modelo aleatório. Depois, apresentamos um estudo similar entre o modelo estocástico e as equações de campo médio para o caso em que cada partícula possui 2 vidas. Finalmente, observamos a cobertura do grafo completo para as equações de campo médio quando o número de vidas por partículas é maior que dois. / We study random walks systems on complete graphs. Initially there is a particle at each vertex of the graph; only one is active and the other are inactive. An active particle performs a discrete-time simple random walk with lifetime depending on the past of the process moving along edges. When an active particle hits an inactive one, the latter is activated. When it jumps on a vertex which has been visited before it dies. The goal of this work is to study the coverage of the complete graph, that is, the proportion of visited vertices at the end of the process, when the number of vertices goes to infinity. We analyze the mean field equations to the process cited above, comparing their results with the ones of the random model. Here the results of the mean field approach seem to reproduce the ones of the random model. After we present a similar study between the stochastic model and mean field approximation to the case that each particle has 2 lifes. Finally we observe the coverage of the complete graph to the mean-field equations when the number of lifes by particle is bigger than two.

Neste trabalho, desenvolve-se um algoritmo detector de PCDs - Plataformas de Coleta de Dados, primeira etapa do processo de regeneração a bordo, que possa ser utilizado nos satélites de coleta de dados da Missão Espacial Completa Brasileira - MECB. Os sistemas atuais utilizam busca no tempo dos vários sinais que chegam aleatoriamente ao receptor. A proposta é utilizar processamento digital de sinais para identificar, no domínio da freqüência, os sinais das PCDs e direcioná-los para os estágios seguintes de demodulação. Para isso, técnicas de estimação espectral foram estudas para se decidir quanto ao método de deteção mais adequado à aplicação. Foram levados em conta, nessa análise, não apenas o desempenho das técnicas de estimação, mas também a complexidade computacional e a capacidade de tratar, em tempo real, sinais com um número de PCDs desconhecido a priori; optando-se pela utilização do estimador direto constituído pelo periodograma com janela de dados temporal prolata de ordem zero. Em paralelo, foi desenvolvido um programa simulador e analisador de sinais, utilizado para avaliar o algoritmo de detecção desenvolvido. Finalmente, o algoritmo de detecção, com aplicação também nos detectores terrenos de PCDs, foi avaliado com sinais simulados e com sinais reais de PCDs,| recolhidos na estação de recepção de sinais de satélites do INPE, em Cuiabá.

Este trabalho apresenta a análise da aquisição do sincronismo das seqüências pseudoaleatórias no receptor GPS (Global Positioning System), que usa a técnica de espalhamento espectral com seqüência direta. A aquisição é feita pela técnica de busca serial "single dwell". A geração de seqüências de máximo comprimento, e suas propriedades aleatórias são estudadas. Os códigos gold utilizados pelo sistema GPS e o sinal pseudoaleatório transmitido são também apresentados. Faz-se uma análise de um circuito digital de recepção para obter a aquisição do sinal pseudoaleatório de acordo com as exigências impostas pelo sistema GPS. São obtidas as equações que permitem calcular analiticamente o tempo médio de aquisição e sua variância. As probabilidades de detecção e falso alarme são encontradas em função dos parâmetros de aquisição, sem considerar o efeito de desvio de freqüência. Finalmente aplica-se a técnica de simulação digital para analisar o desempenho da técnica por busca serial dos sinais pseudoaleatórios, e com ajuda do programa de simulação, torna-se possível avaliar a dupla influência na aquisição quando o efeito Doppler está presente, ou seja, um desvio na freqüência de portadora e um desvio no código pseudoaleatório recebido.