Tese de Mestrado Bruno

Dissertao de Mestrado

Reconstruo de Sinais em Redes de Sensores sem

Fios com Tcnicas de Geoestatstica

Bruno Lopes [email protected]

Orientador:

Alejandro C. Frery

Macei, abril de 2010

Bruno Lopes Vieira

Reconstruo de Sinais em Redes de Sensores sem

Fios com Tcnicas de Geoestatstica

Dissertao apresentada como requisito parcial paraobteno do grau de Mestre pelo Curso de Mestradoem Modelagem Computacional de Conhecimentodo Instituto de Computao da Universidade Fede-ral de Alagoas.

Orientador:

Alejandro C. Frery


Dissertao apresentada como requisito parcial para obteno do grau de Mestre peloCurso de Mestrado em Modelagem Computacional de Conhecimento do Instituto de Com-putao da Universidade Federal de Alagoas, aprovada pela comisso examinadora queabaixo assina.

Alejandro C. Frery - OrientadorInstituto de Computao

Universidade Federal de Alagoas

Eliana S. de Almeida - ExaminadorInstituto de Computao

Universidade Federal de Alagoas

Andr Luiz Lins de Aquino - ExaminadorDepartamento de Computao

Universidade Federal de Ouro Preto


Resumo

As Redes de Sensores sem Fios (RSsF) so conjuntos de dispositivos que obtm amostras defenmenos ambientais, sejam eles naturais (como, por exemplo, temperatura, presso at-mosfrica, intensidade de iluminao, concentrao de substncias em cursos dgua) ouantrpicos (qualidade do ar em sinais de trnsito, presso ao longo de um oleoduto). Essesdispositivos tm despertadomuito interesse, tanto pelas suas potenciais aplicaes quantopelos desafios tericos e tecnolgicos que seu uso otimizado oferece. O objetivo deste traba-lho trata da anlise da reconstruo de sinais nessas redes, com base em tcnicas de geoes-tatstica. Analizam-se trs processos de kriging: simples, ordinrio e bayesiano. Ao simples,analizam-se trs abordagens encontradas na literatura para estimao ou informao do pa-rmetro da mdia e ao bayesiano prope-se uma variante capaz de reduzir o tempo de pro-cessamento necessrio, estimando a mdia por mnimos quadrados generalizados, sendouma constante na inferncia bayesiana. Leva-se em considerao o processo de agrupa-mento dos ns sensores, com simulaes sem agrupamento e com os sensores agrupadospelos algoritmos LEACH e SKATER. O algoritmode kriging bayesiano apresenta osmelhoresresultados qualitativos namaioria dos casos, mas se torna invivel para sistemas que neces-sitem de respostas rpidas. Nesses casos, recomenda-se o algoritmo de kriging ordinrio. Avariante proposta para o kriging bayesiano reduz o tempo de computao, mas no o su-ficiente para sistemas de tempo real. No foram observadas divergncias significativas dequalidade nesta variante.

i

Abstract

Wireless Sensor Networks are a set o mobile devices wich collect datum from the enviro-ment, independet of kind, and transmit them to a data center wich is responsible for takingdecisions. This work aims to analyze the signal reconstruction in these networks using geo-statistic techniques. Three process of kriging are used: simple, ordinary and bayesian. In thesimple kriging, three approaches were found into the literature, according to the way thatthe mean is estimated, and were evaluated. To the bayesian a new approach is proposed:use general least square to estimate the mean and set it as a constant into the bayesian in-ference. The clustering is taked in considered, using simulations without clusters and withclusters formed by LEACH and SKATER algorithms. The bayesian kriging algorithmpresentsthe best qualitative results in almost all scenarios, but it is not available to systems that re-quire fast aswers. In this case we recommend the ordinary kriging algorithm. The proposedvariant of bayesian kriging reduces the time required, but not enough to real-time systems.There were not observed substancial quality differences in this variant.

ii

Agradecimentos

iii

iv

Quem, de trs milnios,No capaz de se dar conta

Vive na ignorncia, na sombra, merc dos dias, do tempo.

JohannWolfgang vonGoethe

Contedo

I Introduo 1

II Geoestatstica,Kriging e as Redes de Sensores sem Fios 3

2.1 Definies iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Modelos de correlao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2.1 Modelo de correlaoMatrn . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2.2 Modelo de correlao exponencial . . . . . . . . . . . . . . . . . . . . . . . 92.2.3 Modelo de correlao esfrico . . . . . . . . . . . . . . . . . . . . . . . . . 92.2.4 Modelo de correlaowave . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.3 Variograma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3.1 Variograma terico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3.2 Variograma emprico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4 Kriging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.4.1 Kriging simples e ordinrio . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.4.2 Kriging bayesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.5 Redes de Sensores sem Fios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.5.1 Agrupamento pelo algoritmo LEACH . . . . . . . . . . . . . . . . . . . . . 212.5.2 Agrupamento pelo algoritmo SKATER . . . . . . . . . . . . . . . . . . . . . 22

2.6 Relao entre a Geoestatstica e as Redes de Sensores sem Fios . . . . . . . . . . 23

III Modelagemproposta 25

3.1 Modelo formulado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.1.1 Sinal de origem amostrado . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.1.2 Processos pontuais e a distribuio dos sensores . . . . . . . . . . . . . . 263.1.3 Reconstruo do sinal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.1.4 Validao domodelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2 Implementao na plataforma R . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.3 Ambiente de execuo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.4 Resultados esperados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

IV Anlise dos resultados 40

4.1 Implementao de simulaes Monte Carlo na literatura . . . . . . . . . . . . . 404.2 Critrios para pesquisa reproduzvel . . . . . . . . . . . . . . . . . . . . . . . . . . 414.3 Dados obtidos com a simulao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.4 Anlise da qualidade do sinal reconstrudo . . . . . . . . . . . . . . . . . . . . . . 43

4.4.1 Anlise do comportamento dos parmetros do modelo . . . . . . . . . . 434.4.2 Anlise do campo gaussiano reconstrudo . . . . . . . . . . . . . . . . . . 45

4.5 Anlise do tempo necessrio reconstruo do sinal . . . . . . . . . . . . . . . . 474.6 Consideraes acerca dos dados obtidos . . . . . . . . . . . . . . . . . . . . . . . 47

v

CONTEDO vi

V Resultados e discusses 48

Referncias bibliogrficas 50

Lista de Figuras

2.1 Exemplos de curvas da correlao Matrn . . . . . . . . . . . . . . . . . . . . . . 82.2 Exemplos de curvas da correlao exponencial . . . . . . . . . . . . . . . . . . . 102.3 Exemplos de curvas da correlao esfrica . . . . . . . . . . . . . . . . . . . . . . 112.4 Exemplos de curvas da correlaowave . . . . . . . . . . . . . . . . . . . . . . . . 122.5 Construo de um variograma terico . . . . . . . . . . . . . . . . . . . . . . . . . 142.6 Examplo de reconstruo por kriging . . . . . . . . . . . . . . . . . . . . . . . . . 172.7 Elementos fundamentais de uma Rede de Sensores sem Fios . . . . . . . . . . . 192.8 Modelo de uma Rede de Sensores sem Fios . . . . . . . . . . . . . . . . . . . . . . 202.9 Clusters de sensores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.10 Clusters gerados pelo LEACH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.11 Sensores espalhados sobre uma superfcie . . . . . . . . . . . . . . . . . . . . . . 222.12 Grafo construdo a partir de 12 sensores . . . . . . . . . . . . . . . . . . . . . . . 232.13 rvore geradoramnima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.14 Clusters formados pelo algoritmo SKATER . . . . . . . . . . . . . . . . . . . . . . 243.1 Exemplos de campos aleatrios gaussianos . . . . . . . . . . . . . . . . . . . . . 263.2 Exemplos de processo pontual Poisson . . . . . . . . . . . . . . . . . . . . . . . . 283.3 Exemplos de processo pontual Poisson no Homogneo . . . . . . . . . . . . . . 293.4 Perspectiva da funo de intensidade . . . . . . . . . . . . . . . . . . . . . . . . . 303.5 Exemplos de processo pontual SSI . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.6 Exemplos do processo compostoC . . . . . . . . . . . . . . . . . . . . . . . . . . 323.7 Exemplos do processo M2P2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.8 Diagrama ilustrativo da reconstruo dos campos gaussianos . . . . . . . . . . . 353.9 Diagrama ilustrativo do sistema de simulaes . . . . . . . . . . . . . . . . . . . 37

vii

Lista de Tabelas

4.1 Plataformas de planilhas eletrnicas avaliadas . . . . . . . . . . . . . . . . . . . . 424.2 Geradores de nmeros pseudoaleatrios de planilhas eletrnicas . . . . . . . . 434.3 Vis e EQM dos estimadores do parmetro . . . . . . . . . . . . . . . . . . . . . 444.4 Mdia dos erros absolutos relativos do kriging . . . . . . . . . . . . . . . . . . . . 454.5 Mdia dos erros absolutos relativos por reconstruo . . . . . . . . . . . . . . . . 464.6 Mdia dos erros absolutos relativos por reconstruo commdia . . . . . . . . 47

viii

Lista de Cdigos

2.1 Algoritmo de kriging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.1 Algoritmo para paralelizao das simulaes . . . . . . . . . . . . . . . . . . . . . 384.1 Reconstruo do campo gaussiano original com base na estimativa . . . . . . . 46

ix

IIntroduo

You need to prepare your students for the future, not the past.

Spencer Graves

R-help (novembro de 2006)

A necessidade de se monitorar reas nas quais no possvel a superviso humana emtodos os pontos tem se tornado cada vez maior. Isso se d, por exemplo, nomonitora-mento de incndios em florestas e na medio de nveis de concentrao de gases txicos;

outro ponto a considerar quando a escala no permite interveno humana, como nomo-

nitoramento da vlvula mitral do corao, utilizandonanosensores e atmesmo quando ela

pode interferir no resultado, como se d no estudo da vocalizao de anfbios, que pode ser

alterado em decorrncia da presena do pesquisador.

Uma dasmais convenientes formas de se obter a automao demonitoramentos o uso

de Redes de Sensores semFios (RSsF, Akyildiz et al., 2002; Szewczyk et al., 2004; Sarangapani,

2007; Sohraby et al., 2007; Wu & Tseng, 2007), que consistem num conjunto de ns sensores

independentes, munidos de dispositivos de sensoreamento e da capacidade de se comuni-

car, transmitindo os dados tipicamente com algum tipo de agregao a um n especial que,

por sua vez, os transmitir a uma central de processamento.

Essa rea ainda recente de pesquisa apresenta diversos problemas em aberto e o Labo-

ratrio de Computao Cientfica e Anlise Numrica (LaCCAN) da Universidade Federal de

Alagoas possui diversos estudos relacionados a estas redes. Dentre eles, a anlise de simula-

dores de RSsF, desenvolvimento de hardware para ns sensores, avaliao do uso de Redes

de Sensores sem Fios no monitoramento de temperatura de Data Centers, medidas de vida

til da rede mediante caractersticas energticas, processos de deposio de ns sensores,

avalio da qualidade da reconstruo de sinais (dados de interesse amostrados) providos

pelas RSsF, dentre outros.

1

INTRODUO 2

Esse ltimo o objetivo deste trabalho. Seguindo as conexes apontadas por diversos au-

tores, como Frery et al. (2010); Alencar-Neto (2008); Aquino et al. (2008); Camilli et al. (2007);

Frery et al. (2008); Jedermann & Lang (2009); Ni et al. (2009) e Umer et al. (2008), este traba-

lho visa avaliar a relao entre as Redes de Sensores sem Fios e a geoestatstica no que con-

cerne reconstruo de sinais.

Com a geoestatstica, os dados esto atrelados a suas posies geogrficas. Adota-

se a hiptese de que o sinal (dado de origem amostrado) estacionrio e, a partir desse

pressuposto, avalia-se a sua reconstruo por alguns processos de kriging (Krige, 1951;

Diggle & Ribeiro Jr., 2007), com uma de suas verses modificada, proposta no captulo 3.

Os algoritmos sero analisados atravs de um estudo Monte Carlo de fora bruta

(Metropolis & Ulam, 1949), analisando-se vis, varincia e erro quadrticomdio apresenta-

dos (definidos no captulo 3) bem como a viabilidade por tempo computacional necessrio.

Namaioria dos cenrios avaliados o algoritmoque apresentoumelhores resultados qua-

litativos foi o kriging bayesiano. Entretanto este necessita de muitos recursos computacio-

nais e grande tempode computao, o que pode inviabilizar o seu uso em cenrios de tempo

real. O kriging ordinrio apresenta o segundo melhor resultato qualitativo, porm com ne-

cessidade de poucos recursos computacionais e processamento de pouco tempo, o que o

tornamais adequado a este tipo de situao. Para os casos em que for necessrio ter amaior

qualidade possvel dos dados e o tempo no for fator crucial, uma variante proposta do kri-

ging bayesiano no apresenta diferenas significativas na qualidade do sinal reconstrudo,

mas possibilita reduo no tempo necessrio para computao.

No captulo 2 encontram-se as principais definies necessrias ao trabalho; a modela-

gem do estudo est definida no captulo 3, com anlise dos dados obtidos no captulo 4 e

discusso dos resultados e trabalhos futuros no captulo 5.

IIGeoestatstica, Kriging e as Redes de

Sensores sem Fios

What we have is nice, but we need something very different.

Robert Gentleman

Statistical Computing 2003 (junho de 2003)

A geoestatstica um ramo da estatstica espacial que difere dos demais por associar osdados s suas posies geogrficas (Bivand & Pebesma, 2008;Diggle & Ribeiro Jr., 2007;Le & Zidek, 2006). Dentre suas tcnicas de inferncia, destaca-se o kriging (Krige, 1951), ori-

ginado nos trabalhos de Daniel G. Krige e Georges Matheron. Sua relao com as Redes

de Sensores sem Fios tem sido discutida em diversos trabalhos, como os de Alencar-Neto

(2008); Camilli et al. (2007); Frery et al. (2008); Jedermann & Lang (2009); Ni et al. (2009) e

Umer et al. (2008).

Neste captulo sero explanados os conceitos necessrios ao entendimento do kriging

bem como suas variaes utilizadas nesse trabalho: simples, ordinrio e bayesiano. Em se-

guida, apresentam-se as definies necessrias ao entendimentodas Redes de Sensores sem

Fios e os algoritmos de agrupamento (clusterizao) utilizados nos experimentos (LEACH e

SKATER).

2.1 Definies iniciais

Nesta seo so explanados conceitos bsicos de probabilidades que fundamentamo traba-

lho que se segue, com base nos textos de James (2006) e Diggle & Ribeiro Jr. (2007).

Definio 1 (Experimento Aleatrio). Um experimento aleatrio consta de uma observao

repetvel no controlada, com um conjunto limitado de resultados observveis.

3

2.1. DEFINIES INICIAIS 4

Definio 2 (Espao Amostral). Dado um experimento aleatrio qualquer, o espao amos-

tral, dito conjunto , consiste no conjunto de todos os resultados que podem ser observados

por este experimento.

Definio 3 (Evento). Seja um conjunto que denota um evento de . Se um con-junto unitrio, diz-se que um evento simples; Pr() = 1, onde o evento dito certo; caso=;, o evento impossvel, isto , Pr(;)= 0.

Definio 4 (Varivel Aleatria Real). Uma varivel aleatria real X uma funo X : R que mapeia os resultados de um experimento aleatrio na reta, onde representa o espao

amostral.

A partir deste ponto, sempre que for referida alguma varivel aleatria, tratar-se- de

uma Varivel Aleatria Real.

Definio 5 (Ocorrncia de uma Varivel Aleatria). Seja X : R uma varivel alea-tria. Uma ocorrncia desta varivel aleatria ser um elemento de R mapeado de que

denota um resultado do experimento aleatrio que X mapeia.

Definio 6 (Distribuio de uma Varivel Aleatria). Conhecer a distribuio de uma va-

rivel aleatria X ser capaz de calcular a probabilidade dela estar num conjuntoA formado

por um nmero arbitrrio de unies e interseces.

Definio 7 (Funo de Distribuio Acumulada). a funo F (t ) = Pr(X t ), t R quecaracteriza cada distribuio. Possui as seguintes propriedades:

1. no decrescente, isto , se t1 < t2, ento F (t1) F (t2);

2. contnua direita, isto , se tn t quando n, ento F (tn) F (t );

3. limt F (t )= 0 e limtF (t )= 1.

Definio 8 (Varivel Aleatria Discreta). Uma varivel aleatria X dita discreta se ela

possui uma quantidade finita ou infinita enumervel de valores possveis. descrita por uma

funo de probabilidade p(ti )= Pr(X = ti ), i = 1,2, . . . , onden

i=1 p(ti )= 1 e 0 p(ti ) 1.

Definio 9 (Varivel Aleatria Contnua). Seja X uma varivel aleatria e F (t ) sua funo

de distribuio acumulada. A funo de densidade de X dada por f (t ) = F (t )/t , quedefine uma varivel aleatria contnua, se f (t ) existir. Suas propriedades so:

1. sempre positiva, ou seja f (t ) 0;

2. sua integral na reta vale 1, entoR

f (t )dt = 1.


Definio 10 (Variveis Aleatrias Distribudas de forma Conjunta). Num experimento

aleatrio onde o interesse est no comportamento conjunto de duas ou mais variveis ale-

atrias, a distribuio conjunta dessas variveis aleatrias ser dada, no caso discreto,

por Pr(X1 = t1 e X2 = t2 e . . . e Xn = tn) = pX1X2 ...Xn (t1i , t2i , . . . , tni ), com o valor do soma-trio

ni=1 pX1X2 ...Xn (t1i , t2i , . . . , tni ) = 1. No caso contnuo, sejam as variveis aleatrias

(X1,X2, . . . ,Xn) sua densidade caracterizada por uma funo fX1,X2 ,...,Xn (t1, t2, . . . , tn), onde:

fX1,X2,...,Xn no negativa;

fX1,X2 ,...,Xn (t1, t2, . . . , tn)dt1,dt2, . . . ,dtn = 1.

Neste trabalho sero tratadas apenas de variveis aleatrias contnuas.

Definio 11 (Esperana de uma Varivel Aleatria). Tambm conhecida por mdia ou

valor esperado, a esperana de uma varivel aleatria X uma mdia ponderada onde os

pesos so dados pelas probabilidades Pr(X = t ). De uma forma genrica definida comoE[X ] =

R

tF (t )dt . No caso discreto definida como E[X ] = i tip(ti ) e no caso contnuoE[X ]= t f (t )dt, se a integral existir.Definio 12 (Esperana de uma Funo). Seja X uma varivel aleatria e (X ) : R Ruma funo qualquer. A esperana de(X ) dada porE[(X )]=

R

(t ) f (t )dt , se a integral

existir.

Definio 13 (Esperana do Produto de Transformaes de Variveis Aleatrias). Sejam

X1, . . . ,Xn variveis aleatrias, a esperana de (X1)(. . . )(Xn), dita E[(X1)(. . . )(Xn)],

ser a integral(t1)(. . . )(tn) f (t1) f (. . . ) f (tn)dt1d . . .dtn no caso contnuo, se a integral

existir; no caso discreto ser o somatrio

i=(t1i )(. . . )(tni ) f (t1i ) f (. . . ) f (tni ).

Definio 14 (Probabilidade Condicional). Sejam X e Y variveis aleatrias. A probabili-

dade condicional Pr(X x | Y = y) dada pela frao

Pr(X x e Y = y)Pr(Y = y) .

Definio 15 (Esperana Condicional). No caso discreto dada por E[X | Y = y] =x xPr(X = x e Y = y). No caso contnuo, E[X | Y ] =

R

x f (x | Y = y)dx, onde, caso X eY possuam distribuio conjunta,

f (x | Y = y)= fXY (x, y)fY (y)

.

Definio 16 (Varincia de uma Varivel Aleatria). Sendo X uma varivel aleatria, o

valor Var(X )=E[X 2]E2[X ], seE[X 2] existir e a diferena estiver bem definida.


Definio 17 (Covarincia dentre Variveis Aleatrias). Sendo X ,Y variveis aleatrias,

definida por Cov(X ,Y )=E[XY ]E[X ]E[Y ], se as esperanas existirem.

Definio 18 (Correlao dentre Variveis Aleatrias). A correlao dentre duas variveis

aleatrias X ,Y dada por Corr(X ,Y )= Cov(X ,Y )pVar(X )Var(Y )

.

Definio 19 (Distribuio Gaussiana). Uma varivel aleatria X segue uma distribuio

gaussiana N (,) de mdia e varincia 2 se possuir funo de densidade

f (t |,)= 1p2pi

exp

{ (t )

2

22

}, (2.1)

,, onde=RR+ o espao paramtrico, com t R.

Definio 20 (Distribuio Gaussiana Multivariada). Dada uma coleo de variveis ale-

atrias X1, . . . ,Xn , elas seguem uma distribuio gaussiana multivariada de mdia =(1, . . . ,n) Rn e matriz de covarincia G simtrica positiva se sua densidade conjunta for

f (t |,G)= 1(2pi)n/2|G |1/2 exp

{12(t )G1(t )

}, (2.2)

onde | | representa o valor do determinante da matriz apresentada neste.

Definio 21 (Processo Estocstico). Um processo estocstico {S(x) : x Rd },d 1 constade uma coleo de variveis aleatrias, onde x Rd representa o posicionamento de cadavarivel aleatria S().

Definio 22 (Processo Estocstico Gaussiano). Para que um processo estocstico {S(x) : x R

d } seja gaussiano, a distribuio conjunta de S(x),x Rd deve ser gaussiana multivariada.Este processo completamente especificado por suas funes demdia e covarincia, respecti-

vamente:

(x)=E[S(x)],Cov{S(xi ),S(x j )}=E[S(xi )S(x j )]E[S(xi )]E[S(x j )].

Definio 23 (Processo Estocstico Estacionrio). Umprocesso estocstico diz-se estacion-

rio se suamdia for constante igual a e a covarincia depender apenas da diferena vetorial

entre xi e x j : Cov{S(xi ),S(x j )} = (u), u = xi x j , assim (u) = Cov{S(z),S(z + u)}; comoCov{S(zi ),S(z j )} = Cov{S(zi +h),S(z j +h)}, pode-se utilizar qualquer valor para z dentro dodomnio admissvel.

Definio 24 (Processo Estocstico Estacionrio Isotrpico). A propriedade de isotropia

num processo estocstico {S(x) : x Rd } obtida quando a diferena vetorial dentre duas va-riveis aleatrias dada pela distncia euclidiana. Assim, (xi ,x j ) = (u), com deno-tando distncia euclidiana.

2.2. MODELOS DE CORRELAO 7

Definio 25 (Campos Aleatrios). Um campo gaussiano definido por um processo esto-

cstico {S(x) : x Rd }, onde d representa a dimenso do espao. So comumente utilizadospara representar fenmenos naturais, como iluminao, umidade, temperatura etc. Sua ca-

racterizao se d pela distribuio conjunta de suas variveis aleatrias.

Definio 26 (Estimador). Um estimador uma funo de variveis aleatrias que, em

princpio, tenta aproximar o valor verdadeiro de um parmetro de uma distribuio.

Neste trabalho sempre que for referido um campo gaussiano tratar-se- de um campo

aleatrio cuja distribuio conjunta de suas variveis aleatrias gaussianamultivariada.

2.2 Modelos de correlao

Uma funo paramtrica (u) deve ser definida para o domnio R+ para que cumpra os

requisitos de uma funo de correlao. Se ela vlida para Rd , ser tambm para Rm ,

m < d , mas no necessariamente para dimenses maiores.Essas funes costumam decrescer quando u = xi x j aumenta emmodelos estacio-

nrios e interessante que possuam diferentes graus de suavizao (ver figuras 2.1a e 2.2a).

Ou seja, que haja fatores que suavizem suas curvas. Seguem informaes sobre alguns mo-

delos de correlao, aplicados a um processo estocstico gaussiano estacionrio isotrpico

{S(x) : x R2}.

2.2.1 Modelo de correlaoMatrn

O modelo de correlao Matrn um dos mais utilizados na literatura. Ele apresenta duas

propriedades extremamente interessantes aos estudos de geoestatstica: depende apenas

do posicionamento geogrfico dos dados e possui um parmetro de suavizao da curva

entre dois pontos (Diggle & Ribeiro Jr., 2007).

Sua representao dada na forma

(u)={2(1)()

}1 (u

)K

(u

), (2.3)

onde K() representa uma funo de Bssel de ordem , > 0 um parmetro de escala,responsvel por dimensionar a distncia, e > 0 o parmetro responsvel pela curva desuavizao dentre os valores, denomina-se ordem.

A figura 2.1a mostra a curva da correlao deMatrn de acordo com o aumento do valor

u, onde o quo mais clara for a linha, maior o valor de , com 0,5 2,5, com fixo em0,23. Da mesma forma a figura 2.1b apresenta os resultados com = 2 e 0,1 0,3.


0.0 0.2 0.4 0.6 0.8 1.0

0.0

0.2

0.4

0.6

0.8

1.0

u

(u)

(a) Variao do parmetro

0.0 0.2 0.4 0.6 0.8 1.0

0.0

0.2

0.4

0.6

0.8

1.0

u

(u)

(b) Variao do parmetro

Figura 2.1: Exemplos de curvas da correlao Matrn onde o parmetro varia de forma quequomais clara for a cor da linha, maior o valor do parmetro


Para= 0,5, a correlaoMatrn reduz-se a exponencial (seo 2.2.2), (u)= exp{u/},e para , (u) exp{(u/)2}, tambm conhecida como funo de correlao gaussi-ana (Handcock &Wallis, 1994).

Vale ressaltar que correlaes de ordem ou escala diferentes no so comparveis. A

partir da, sugere-se uma reparametrizao da funo para = 2p.

2.2.2 Modelo de correlao exponencial

Assim como omodeloMatrn, o exponencial apresenta umparmetro de suavizao e um

de escala (Diggle & Ribeiro Jr., 2007). Entretanto, est limitado a 0. (2.5)

Consoante no possuir parametrizao para suavizao da curva, seu modelo apresenta

uma grande vantagem: um limitantefinito de distncia. Para valores suficientemente grades

de distncia, leia-se u > , o valor da correlao ser (u) = 0. Um exemplo de suas curvasest exposto na figura 2.3 com 0,1 0,3.

Alm de perder flexibilidade pela parametrizao, um outro problema presente o fato

dessa funo de correlao ser apenas uma vez diferencivel para u = . Isto proporcionadificuldades na estimao por mxima verossimilhana.


0.0 0.2 0.4 0.6 0.8 1.0

0.2

0.4

0.6

0.8

1.0

u

(u)

(a) Variao do parmetro

0.0 0.2 0.4 0.6 0.8 1.0

0.0

0.2

0.4

0.6

0.8

1.0

u

(u)

(b) Variao do parmetro

Figura 2.2: Exemplos de curvas da correlao exponencial onde o parmetro varia de formaque quomais clara for a cor da linha, maior o valor do parmetro

2.3. VARIOGRAMA 11

2.2.4 Modelo de correlao wave

Modelos nomontonos de correlao so raros. Um exemplo a funoWave,

(u)=(u

)1sen

(u

). (2.6)

Assim como o esfrico, ele tambmuniparametrizadopela escala (). Seu comportamento

pode ser observado na figura 2.4 com 0,1 0,3.

0.0 0.2 0.4 0.6 0.8 1.0

0.0

0.2

0.4

0.6

0.8

1.0

u

(u)

Figura 2.3: Exemplos de curvas da correlao esfrica comvariao doparmetrode formaque quomais clara for a cor da linha, maior o valor e

Outros modelos de correlao podem tambm ser encontrados na literatura (ver, por

exemplo, Gneiting, 1997; Schlather, 1999). Entretanto, esses apresentados so os mais utili-

zados em geoestatstica.

2.3 Variograma

Tambm conhecido por semivariogramaou semivarincias, o variograma uma ferramenta

muito importante geoestatstica. Ele descreve naturalmente estruturas de dependncia

nummodelo gaussiano e pode ser til como ferramenta de diagnstico nos demais.

2.3. VARIOGRAMA 12

0.0 0.2 0.4 0.6 0.8 1.0

0.

20.

00.

20.

40.

60.

81.

0

u

(u)

Figura 2.4: Exemplos de curvas da correlao wave com variao do parmetro de formaque quomais clara for a cor da linha, maior o valor de

2.3.1 Variograma terico

Num processo estocstico o variograma terico dado pela funo V (xi ,x j )= 12Var{S(xi )S(x j )}. No caso de um processo estacionrio (assim como exposto na definio 23) o va-

riograma se reduz a uma funo de u = ||xi x j || e (u) = Cov{S(x),S(x u)} equivalente,expressa por VY (u) = (0) (u) = 2{1 (u)}, onde 2 a varincia de S(x) e (u) =Corr{S(x),S(xu)}. Como a mdia constante:

VY (u)=1

2E

[{S(x)S(xu)}2

]. (2.7)

2.3.2 Variograma emprico

Dado um conjunto de variveis aleatrias Yi : i = 1, . . . ,n que modelam os dados do fen-meno mesurado e yi : i = 1, . . . ,n ocorrncias dessas variveis, os valores vi j = 12(Yi Y j )2correspondem a uma estimativa no viesada da semivarincia, tambm denominada vario-

grama ordinrio.

O variograma tericoVT ser os pares de distncias e variogramas ordinrios correspon-

dentes (ui j ,vi j ) : j > i . Graficamente, ele correponde a plotagem dos valores vi j pelas dis-tncias correpondentes (ver exemplo na figura 2.5b, construdo a partir dos pontos amos-

2.4. KRIGING 13

trados no campo gaussiano da figura 2.5a).

2.4 Kriging

Dado S(), que modela um sinal (dado de interesse) ocorrido, porm no observado,pretende-se efetuar predio sobre ocorrncias de uma varivel aleatria T = T (S), ondeT denota o conjunto de variveis aleatrias que sero preditas, S representa o conjunto de

todos os valores a partir de S(x) e T () a funo de predio.Sejam amostras observadas Y = (y1, . . . , yn) onde cada yi representa uma amostra, com

possvel rudo, de seu correspondente S(x), num processo estocstico gaussiano estacion-

rio {S(x) : x R2} com x representando o posicionamento geogrfico. S possui distribuiogaussiana multivarada de vetor de mdias 1, onde 1 um vetor onde todos os elementos

so 1. Suamatriz de varincia 2R , onde R nn tal que ri j = (||xi x j ||).Da mesma fora Y possui distribuio gaussiana multivariada com vetor de mdias 1 e

matriz de varincia

2V = 2(R+v2I )2V = 2R+2I , (2.8)

com I sendo a matriz identidade.

Utilizando qualquer funo t de Y tal que T = t (Y ) o erro do preditor pelos mnimosquadrados ser:

MSE(T )=E[(T T )2] . (2.9)A forma que minimiza esta quantidade dada quando T =E[T | Y ]. Da, tem-se que:

E[(T T )2]=EY [Var(T | Y )]. (2.10)

Neste trabalho so analisadas algumas variantes do processo de kriging (Krige, 1951),

que, de uma forma geral, consistem no resultado de

S(x)=WwiS(x)dx, (2.11)

onde S(x) denota o conjunto de amostras,W R2 a janela deR2 que o processo estocs-ticomodela e wi : i = 1, . . . ,n um vetor de pesos, construdos a partir das funes de correla-o, que suavizam a interpolao dentre os pontos (Diggle & Ribeiro Jr., 2007).

2.4. KRIGING 14

(a) Campo gaussiano com pontos em destaque amostrados

0 20 40 60 80 100

010

20

30

40

u

V(u

)

(b) Variograma emprico

Figura 2.5: Campo gaussiano com pontos amostrados em 2.5a, a partir dos quais se constrio variograma emprico em 2.5b

2.4. KRIGING 15

2.4.1 Kriging simples e ordinrio

Dentre todos os modelos de kriging, o simples apresenta-se como o modelo matemtico

mais simples. Nele se considera que mdias de grupos dos valores do processo se apro-

ximam da mdia global. Relaxando-se essa suposio, de forma a permitir que as mdias

locais possam se distanciar da global, o kriging ordinrio usa uma estimao diferente para

a mdia.

Em suma:

no kriging simples a mdia informada e todos os demais parmetros so tratados

como conhecidos, entretanto, necessrio acoplar estimadores dos demais parme-

tros ao preditor;

no kriging ordinrio, a mdia tratada como parmetro desconhecido, sendo substi-

tuda pelo estimador por mnimos quadrados

= (1V 11)11V 1Y . (2.12)

Alguns autores, entretanto, adotam que no kriging simples a mdia no informada,

mas computada atravs dos mnimos quadrados ordinrios dos valores amostrados, dito y

(Diggle & Ribeiro Jr., 2007, pp. 137). Entretanto, essa abordagem pode no resultar em bons

valores estimados; uma alternativa utilizar os mnimos quadrados generalizados, levando

em considerao os valores de covarincia dentre as variveis indexadas pelas coordenadas

amostradas.

O preditor de kriging para T = S(x) ser

T =+ r V 1(Y 1), (2.13)

onde r o vetor tal que ri = (||x xi ||), i = 1, . . . ,n1 e V dado por (2.8). Y possui distri-buio gaussianamultivariada de mdia 1 e matriz de varincia dada por (2.8).

Da, segue que

S(x)=+ni=1

ai (x)(Yi )=[1

ni=1

ai (x)

]+

ni=1

ai (x)Yi . (2.14)

O preditor por kriging ordinrio pode ser expresso como S(x) =ni=1wi (x)Yi , onde w o vetor de pesos do kriging para o ponto xi . Ou seja, dado um ponto no amostrado xi o

qual deseja-se reconstruir com base no conjunto de amostras Y , ser computado um vetor

de pesos w , com a soma de seus elementosn

i=1wi = 1. Esse vetor de pesos w ser nicopara cada i .

SeVY () a funo de semivarincia (semivariograma) de umprocesso estocstico gaus-siano estacionrio {S(x) : x R2}, onde x denota o posicionamento geogrfico dos pontos, o

2.4. KRIGING 16

vetor de pesos para um ponto xi ser dado por

w1VY (ui ,x1 )+ +wnVY (ui ,xn )=VY (ui ,xi ), (2.15)

no kriging simples.

Para o kriging ordinrio, insere-se na equao uma varivel de normalizao . Assim, a

equao que representa o vetor de pesos w para o kringing ordinrio

w1VY (ui ,x1)+ +wnVY (ui ,xn )+=VY (ui ,xi ), (2.16)

onde possui o mesmo valor, independente de i .

Em ambos os casos o vetor de pesos definido pela resoluo de um sistemade equaes

baseadas na semivarincia. Da nota-se o impacto do modelo de correlao adotado no

kriging, que parte da definio de semivarincia e a construo dos pesos de forma aprover

curvas de variao suaves, determinadas por seus fatores de suavizao ().

Como os modelos de kriging simples e ordinrio diferem apenas na estimao damdia

por este ltimo, o kriging simples tambm conhecido como kriging ordinrio com mdia

(Diggle & Ribeiro Jr., 2007).

A escolha de um modelo que represente o mais adequadamente o possvel os dados

crucial para que se obtenha um bom resultado. Da mesma forma, encontrar valores de

que se aproximem do ideal proporcionar uma reconstruo omais fidedgna o possvel.

Uma descrio algoritmica do processo de kringing est no cdigo 2.1. Como ilustra-

o dos resultados que se podem obter atravs das duas tcnicas a figura 2.6 apresenta um

campo gaussiano em 2.6a com 20 pontos amostrados e reconstrudos por kriging simples e

ordinrio, respectivamente 2.6b e 2.6c.

1 S

2.4. KRIGING 17

(a) Campo aleatrio original

(b) Reconstruo por kriging simples (c) Reconstruo por kriging ordinrio

Figura 2.6: Dada uma regio de interesse 2.6a, amostram-se alguns pontos atravs de 20 sen-sores dispostos aleatoriamente e reconstri-se a partir desses dados amostrados por krin-ging simples 2.6b e ordinrio 2.6c

2.4.2 Kriging bayesiano

Diferentemente dos modelos anteriores de kriging, o bayesiano no faz nenhuma distin-

o formal entre os pontos no observados e os parmetros do modelo a serem estimados.

Conforme Diggle & Ribeiro Jr. (2007), ambos so tratados como variveis aleatrias no ob-

servadas.

Seus principais requisitos so:

conhecimento da distribuio a priori de , onde o espao paramtricodo processo estocstico modelado que, como nos demais, gaussiano estacionrio

{S(x) : x R2};

capacidade computacional para a especificao de ummodelo com seus dados a pri-

2.4. KRIGING 18

ori a serem computados a posteriori.

Um dado a priori uma informao parametrizada aomodelo. Por sua vez uma a poste-

riori inferida nomodelo atravs da informao a priori.

A capacidade computacional citada trata de resolver a seguinte equao:

Pr( | y)= `(; y)pi()`(; y)pi()d

, (2.17)

onde as funes utilizadas so a de verossimilhana,`(; ), e a distribuio apriori,pi(), dadapelo teorema de Bayes (2.18). O parmetro y corresponde aos dados amostrados, ocorrn-

cias de S(x).

O Teorema de Bayes diz que

Pr(A | B)= Pr(B | A)Pr(A)Pr(B)

. (2.18)

Neste caso Pr(A) e Pr(B) seriam as probabilidades a priori e Pr(A | B) e Pr(B | A) as probabi-lidades a posteriori.

No enfoque bayesiano, o modelo pode ser especificado como [Y ,], onde Y representa

as variveis aleatrias que descrevem o fenmeno a ser reconstrudo (o sinal), so todos

os parmetros do modelo a serem inferidos e [] denota a distribuio das variveis alea-trias que lhe so parametrizadas. Assim, com os valores a priori de pode-se calcular a

[Y ,] = [Y | ][], onde a notao | denota condicionalidade dentre as variveis aleatrias.Pelo Teorema de Bayes, apresentado na equao (2.18), chega-se a

[ | Y ]= [Y | ][][Y ]

, (2.19)

onde [Y ] pode ser obtido por

[Y ]=[Y | ][]d, (2.20)

induzido pela funo de verossimilhana. As inferncias acerca do parmetro so feitas por

computao de dados a posteriori, com [ | Y ].Modelando o proposto neste trabalho com o enfoque bayesiano tem-se trs elementos:

um sinal no observado, S; um conjunto de valores medidos, Y ; e os parmetros domodelo,

. A especificao do modelo, ento, se d por

[Y ,S,]= [][S | ][Y | S,]. (2.21)

Como [] representa os valores a priori de , eles podem ser encarados como a opinio do

analista dos dados. Sob a aplicao do Teorema de Bayes, equao (2.18),

[S | Y ]=[S | Y ,][ | Y ]d. (2.22)

2.5. REDES DE SENSORES SEM FIOS 19

Algoritmicamente, iniciandopelo valor inicial arbitrado, sero computados os valores in-

feridos. Com estes calculados, os parmetros do modelo so computados (inferncia sobre

) e o processo se repete at um limite de convergncia pr-estabelecido.

Nesse trabalho sero avaliadas computaes com o valor de mdia conhecido e infe-

rido por mdia ponderada, levando em considero valores inferidos de correlao. Em

uma abordagem real a uma Rede de Sensores sem Fios (ver seo 2.5), efetua-se um pro-

cedimento de flood (disperso da solicitao de leitura de dados a todos os sensores que

a retornaro conforme a modelagem da rede) e esses dados so utilizados para compor a

mdia.

2.5 Redes de Sensores sem Fios

AsRedes de Sensores semFios (RSsF Akyildiz et al., 2002; Szewczyk et al., 2004; Sarangapani,

2007; Sohraby et al., 2007;Wu & Tseng, 2007) so conjuntos de dispositivosque obtmamos-

tras de fenmenos ambientais, sejam eles naturais (como, por exemplo, temperatura, pres-

so atmosfrica, intensidade de iluminao, concentrao de substncias em cursos dgua

ver figura 2.7) ou antrpicos (qualidade do ar em sinais de trnsito, presso ao longo de um

oleoduto). Uma vez comessas informaes captadas, elas so transmitidas a umn especial,

denominado sink que tipicamente efetua algum tipo de agregao de dados, numa comu-

nicao atravs de redes ad-hoc (Rappaport, 2002; Sarangapani, 2007; Sohraby et al., 2007;

Wu & Tseng, 2007). Este se responsabiliza por transmitir as informaes coletadas atravs de

algummeio como a Internete para um centro de tratamento de dados e tomada de decises,

o qual pode efetuar consultas na rede. Seu funcionamento pode ser modelado conforme o

diagrama da figura 2.8, modelado por Frery et al. (2010).

SensoresMeio

Sink

Central

Figura 2.7: Elementos fundamentais de uma Rede de Sensores sem Fios


NF V S V V F V

Ry RyD D

Figura 2.8: Modelo de uma Rede de Sensores sem Fios

No diagrama supracitado, N representa a natureza, com toda sua infinidade de fatos, F

o fenmeno de interesse (o sinal, i.e.: iluminao, temperatura, umidade etc.), com todos

os seus dados em V . Se fosse possvel observar F em toda a sua complexidade, constuir-se-

a um conjunto de regras ideais R com as quais seria possvel tomar decises ideaisD. Em

vez disso, utiliza-se um conjunto de sensores S = {S1, . . . ,Sn} que disponibiliza um conjuntode valores V , sob os quais efetuam-se transformaes (i.e.: agregao e fuso de dados)

que geram um conjunto de dadosV . Nesse ltimo conjunto de dados aplica-se uma funo

de reconstruo do sinal F que permite idealmente reconstruir o conjunto de valores V

a partir do qual pode-se construir um conjunto de regras R com as quais se pode tomar

decises D . Este conjunto D deve ser o mais prximo possvel deD (idealmente iguais).

Essas redes tm despertado muito in-

Figura 2.9: Clusters de sensores

teresse, tanto pelas suas potenciais aplica-

es quanto pelos desafios tericos e tec-

nolgicos que seu uso otimizado oferecem.

Tipicamente aplica-se algumalgoritmopara

reduzir a quantidade de dados transmitidos

(Nakamura et al., 2007). Dentre os princi-

pais motivos para que se efetue esta ope-

rao, est que a transmisso de dados co-

mumente a operaomais custosa em ter-

mos de energia (Akyildiz et al., 2002). As-

sim,minimizando essas transmisses pode-

se prolongar o tempo de vida til da rede.

Bem como esta compactao, h diver-

sos outros aspectos tecnolgicos, como autoconfigurao, adaptao na ocorrncia de fa-

lhas e limitaes de energia, aguardando por solues satisfatrias. Uma das formas de oti-

mizar o consumo de energia utilizar agrupamentos (clusters) de sensores. A tcnica con-

siste em formar grupos de sensores que transmitem seus dados a um n dentro do grupo,

para que somente este transmita as informaes ao destino. Os grupos so definidos e

eleito um dito representante (clusterhead) responsvel por receber as informaes dos de-

mais sensores e transmit-lo (ver figura 2.9).


Essa a idia dos algoritmos LEACH e SKATER, dentre diversos outros (ver Akyildiz et al.,

2002; Heinzelman et al., 2002; Younis & Fahmy, 2004; Assuno et al., 2006; Younis et al.,

2006; Yoon & Shahabi, 2007; Abbasi & Younis, 2007). O objetivo sempre o mesmo: analisar

globalmente o estado da rede para formar grupos de sensores e estratgias de fuso de in-

formaes, diminuindo a redundncia nos dados transmitidos e otimizando o consumo de

energia. Dessa forma o consumo minimizado nos sensores que apenas transmitem para

este representante do grupo. Alm disso, pode-se aplicar alguma transformao nesses da-

dos no nvel dos clusters, como por exemplo no caso de medio de temperatura transmitir

a mdia de cada grupo, em vez da informao de cada sensor.

As principais referncias que tratam deste assunto no empregam explicitamente a ana-

logia existente entre esse problema e o problema de amostragem e reconstruo de sinais.

Alencar-Neto (2008) e Frery et al. (2008) estabelecem formalmente essa analogia, e propem

medidas de erro na reconstruo do sinal empregando diferentes tcnicas de amostragem e

de reconstruo (ambas utilizando clulas de Voronoi).

A dissertao demestrado deAlencar-Neto

Figura 2.10: Clusters gerados pelo LEACH,com clusters identificados pelas cores atribu-das aos sensores

(2008) generaliza esses resultados, conside-

rando (alm da amostragem e da recons-

truo por clulas de Voronoi) amostragem

baseada em funes caractersticas dos sen-

sores (dando, assim, maior realismo ao es-

tudo) e kriging simples na reconstruo do

sinal. Esta ltimamostrouproduzir resulta-

dos significativamente melhores do que os

gerados pela reconstruo por Voronoi na

maioria dos casos.

2.5.1 Agrupamentopelo algoritmo

LEACH

O algoritmo LEACH (Low Energy Adaptive Clustering Hierarchy Heinzelman et al., 2000,

2002) prope a diviso dos ns sensores numaquantidade pr-definidade clusters. Escolhem-

se aleatoriamente os clusterheads e os integrantes de cada grupo so definidos atravs de

uma funo queminimize a distncia entre osmembros de um cluster e seu clusterhead (ver

figura 2.10).

Esse processo ocorre numa etapa de configurao, prvia ao inicio do sensoriamento.

Determina-se uma janela de tempo em que essa configurao permanece at que haja a

reconfigurao da rede, onde os clusterheads se alternam, numa tentativa de minimizar o

desgaste desses sensores, visto que eles promovemmais comunicao, gastandomais ener-

gia.


Neste protocolo h uma srie de fatores no especificados e ainda h a premissa de que

cada clusterhead comunica-se diretamente como sink, semnecessitar transmitir dados para

outros sensores e que estes os repassem (comunicao single-hop). Entretanto, em diversos

casos esse escopo no retratar uma situao real. Dentre as diversas variaes deste proto-

colo encontradas na literatura,muitas que desconsideram essa restrio.

2.5.2 Agrupamento pelo algoritmo SKATER

Uma outra alternativa para o processo de agrupamento de sensores o protocolo SKATER

(Spatial Kluster Analysis by Tree Edge Removal Assuno et al., 2006). A abordagem ado-

tada prover grupos com dados o mais correlacionados o possvel.

Os sensores so organizados num grafo onde cada um determina um vrtice. As arestas

so definidas pelo raio de comunicao (ver figura 2.12, que apresenta o grafo correspon-

dente aos sensores da figura 2.11).

Figura 2.11: Sensores espalhados sobre uma superfcie

Dado que um sensor consegue se comunicar com outro, atribui-se um peso a aresta que

representa a distncia entre os dados amostrados naquele instante pelos sensores. Conside-

rando esses pesos calcula-se uma rvore geradora (subgrafo contendo todos os vrtices do

grafo original, enretanto apenas um caminho de um n a outro, conforme a figura 2.13) de

customnimo (a soma dos pesos das arestas para se percorrer de um vrtice a outro possuir

o menor valor possvel).

Dessa rvore subtraem-se as n arestas de maior peso, onde n representa a quantidade

desejada de clusters. Os subgrafos resultantes conexos definem cada um dos grupos (ver

figura 2.14). Note-se que os clusterheads no possuem fator determinante na formao dos

clusters.

2.6. RELAO ENTRE A GEOESTATSTICA E AS REDES DE SENSORES SEM FIOS 23

1110

1

0

3 2

5 4

76

9

85,27

3,02

1,01

3,62

2,51

4,24

0,49

1,61

3,23

4,63

1,77

1,31

0,45

1,65

1,48

5,46

2,76

4,71

2,20 1,80

3,81

0,56

2,27

2,01

1,97

1,03

0,79

4,56

1,603,98

0,26

0,07 1,52

2,10

0,75

2,83

1,71

1,24

0,75

3,26

3,06

2,47

3,21

5,42

0,17

0,19

2,36

5,72

2,27

3,32

2,95

2,21

0,960,82

1,46

3,75

0,86

Figura 2.12: Grafo construdo a partir de 12 ns sensores (0 a 11)

1110

1

0

3 2

5 4

76

9

8

0,49

1,61

1,48

0,56

0,79

0,26

0,07

0,750,17

0,19

0,96

Figura 2.13: rvore Geradora Mnima do grafo de sensores da figura 2.12

Assim, os grupos devero conter os sensores de dados amostradosmais correlacionados.

Bemcomonoprotocolo LEACH, h etapas de configurao e reconfigurao,paraminimizar

o desgaste energtico nos clusterheads.

2.6 Relao entre aGeoestatstica e as Redes de Sensores sem

Fios

O objetivo deste trabalho avaliar a conexo entre a geoestatstica e as Redes de Senso-

res sem Fios, apontada j por Frery et al. (2010); Alencar-Neto (2008); Aquino et al. (2008);

Camilli et al. (2007); Frery et al. (2008); Jedermann & Lang (2009); Ni et al. (2009); Umer et al.

(2008). Para tal, no captulo 3 ser construdo ummodelo de simulaes.

O ambiente simulado o de Redes de Sensores sem Fios nos mais diversos cenrios de

2.6. RELAO ENTRE A GEOESTATSTICA E AS REDES DE SENSORES SEM FIOS 24

1110

1

0

3 2

5 4

76

9

8

0,49

1,61

1,48

0,56

0,79

0,26

0,75

0,19

0,96

Figura 2.14: Diviso dos sensores da figura 2.12 em 3 clusters pelo algoritmo SKATER

dados. Neles, so aplicados os dois algoritmos de agrupamento definidos na seo 2.5 que

provem os dados amostrados. Com estes dados, aplicam-se os algoritmos de kriging defi-

nidos nas sees 2.4.1 e 2.4.2 e os sinais reconstrudos so avaliados.

Uma proposta de modificao no algorito definido pela seo 2.4.2 tambm efetuada,

visando no s ganho no resultado do sinal obtido bem como no custo computacional.

IIIModelagem proposta

R may be the wrong tool for the job, but its the wrong job.

Rolf Turner

R-help (maio de 2008)

A avaliao dos algoritmosde reconstruo de sinais apresentadosno captulo 2 foi efetu-ada atravs de simulaesMonteCarlo implementadas na plataforma R. Neste captuloseguem os detalhes da modelagem e implementao do sistema de simulaes e de como

os dados foram gerados.

3.1 Modelo formulado

O cenrio de simulaes foi montado atravs de umprocesso estocstico gaussiano estacio-

nrio isotrpico {S(x) : x R2}, onde x denota a posio geogrfica das variveis aleatrias.Os dados so amostrados na forma (x, y), onde y representa uma ocorrncia da varivel ale-

atria S(x).

Seguem novas definies necessrias a compreenso da implementao domodelo.

3.1.1 Sinal de origem amostrado

Os dados utilizados nas simulaes so provenientes de campos aleatrios gaussianos

{S(x) : x R2} gerados pelos mtodos apresentados por Chan &Wood (1997); Lantuejoul(2002) e Schlather (1999).

Neste trabalho adotou-se omodeloMatrn (ver seo 2.2.1), citado comomodelo de cor-

relaomais utilizado em geoestatstica (Bivand & Pebesma, 2008; Diggle & Ribeiro Jr., 2007;

Le & Zidek, 2006), para as variveis aleatrias do campo gaussiano. Assim, pode-se variar os

25

3.1. MODELO FORMULADO 26

parmetros deste modelo de forma a gerar situaes diversas. Os parmetros variados so

mdia, varincia, coeficiente de suavizao () e escala (). Este ltimo permite modelar,

dentre outras aplicaes, a intensidade da luz que chega ao solo de uma floresta, em funo

da densidade da folhagem das rvores (ver Alencar-Neto, 2008).

A partir deste ponto, sempre que for referido um campo gaussiano ele ter mdia zero

e varincia unitria. Exemplos de campos aleatrios gaussianos com parmetros variados

podem ser vistos na figura 3.1.

(a) = 1 e = 1 (b) = 1 e = 5

(c) = 5 e = 1 (d) = 5 e = 5

Figura 3.1: Exemplos de campos aleatrios gaussianos de 100100 pontos, mdia 0 e vari-ncia 1, variando parmetros de suavizao () e escala (), onde utiliza-se uma escala decores para representar a mudana de valores

3.1.2 Processos pontuais e a distribuio dos sensores

A distribuio dos sensores segue o modelo proposto por Alencar-Neto (2008); Frery et al.

(2008), utilizandoprocessos pontuais (Baddeley, 2006) para distribuir os ns sensores. Estes,


somodelos estocsticos que descrevem a distribuio de dados no espao. Para a compre-

enso do modelo adotado, necessrio incluir algumas definies com base nos textos de

James (2006); Alencar-Neto (2008), a saber.

Definio 27 (Processo Estocstico Poisson). Sendo Ekt ,t a notao para k eventos ocorridos

no intervalo de tempo (t , t +t ], a distribuio de um processo de Poisson pode ser definidacomo Pr(Ek0,t )= (t )ket/k ! Sua caracterizao se d pelo parmetro de intensidade e peloparmetro , com a relao (t )= t , que denota a quantidade esperada de eventos por uni-dade de tempo. As seguintes hipteses seguem da probabilidade acima:

1. Pr(Ekt ,t+t )= Pr(Ek0,t ), k, t e t ;

2. Pr(Ek1t1,t1 Ek2t2,t2

)= Pr(Ek1t1,t1 )Pr(Ek2t2,t2

) se (t1,t1] (t2,t2]=;;

3. limt0

Pr(Ea0,t )

Pr(Eb0,t )= 0, com a 2 e b 1.

Definio 28 (Processos pontuais Homogneos com Independncia). So processos pon-

tuais onde a quantidade de eventos esperados (parmetro ) constante, ou seja, dado um

processo {S(x) : x Rd }, (x)=> 0,x Rd .

A partir deste ponto, considere-se todo processo estocstico com dimenso 2.

Definio 29 (Distribuio Uniforme). Uma varivel aleatria contnua X : {x R : x } segue a distribuio uniforme se sua densidade for dada pela funo f (t ) =()11(a,b)(t ), com 0 e > 0. p1,p2, . . . ,pn representam os pontos deste processo em um subconjuntoA Rd , onde o nmero de pontos de qualquer conjunto B A, denominado N (B) possuir asseguintes propriedades:

1. N (B) segue uma distribuio de Poisson de mdia (B) definida porB (u)du, tal que

(u) constante para todo u B;


2. as variveis aleatrias N (B1), . . . ,N (Bn) so coletivamente independentes se os conjun-

tos B1, . . . ,Bn forem disjuntos.

A partir da, um processo pontual Binomial ser um processo pontual de Poisson condicio-

nado ao nmero de pontos n. Exemplos de processos pontuais Poisson podem ser observados

na figura 3.2. Estes podem ser encarados como exemplos de processos pontuais binomiais com

n dado em 3.2a, 3.2b, 3.2c e 3.2d.

(a) n = 94 pontos (b) n = 95 pontos

(c) n = 100 pontos (d) n = 94 pontos

Figura 3.2: Exemplos de um processo pontual de Poisson com = 100

Definio 33 (Processos pontuais no homogneos). Num processo pontual no homog-

neo a intensidade do parmetro pode variar de acordo com a rea onde o processo apli-

cado. Assim possvel construir processos onde a probabilidade de se obter n pontos varie em

decorrncia da rea de A em questo. Pode-se construir um processo desse tipo definindo sua

intensidade como uma funo tal que : AR+ comB


Definio 34 (Processo pontual Poisson no homogneo). umconjunto de pontos P1, . . . ,Pn

localizados num conjunto A R2 tal que o nmero de pontos N (B) de qualquer B A possuias seguintes propriedades:

1. N (B) segue umadistribuio de Poisson demdia(B) tal que (u) varia de acordo com

a funo de intensidade : AR+ qualquer que seja u B;

2. as variveis aleatrias N (B1), . . . ,N (Bn) so coletivamente independentes se os conjun-

tos B1, . . . ,B2 forem disjuntos.

Exemplos de um processo de Poisson no homogneo podem ser observados na figura 3.3

com (x, y)= xex , cujo comportamento pode ser observado na figura 3.4.

(a) = 10 (b) = 50

(c) = 75 (d) = 100

Figura 3.3: Exemplos de um processo pontual de Poisson no Homogneo com (x, y) =xex


Figura 3.4: Perspectiva da funo de intensidade (x, y)= xex

Definio 35 (Processo Pontual SSI Matrns Simple Sequential Inhibition). Define-se de

forma iterativa, com tentativas de por n pontos atravs de uma distribuio uniforme de m-

dia 2n numa regio A. Com um parmetro de distanciamento obrigatrio (raio de inibio)

r , insere um primeiro ponto em A e efetuam-se at T tentativas para cada um dos n1 pon-tos restantes, sendo estas bem sucedidas se nenhuma das distncias entre este ltimo ponto e

quaisquer outro for menor ou igual a r , caso contrrio, o ponto descartado. Na figura 3.5

pode-se observar exemplos de um processo SSI de n = 100, T = 1.000 e raio de inibio vari-ando em r = {0,01, 0,05, 0,10, 0,11}.

Uma vez definidos esses processos pontuais, pode-se definir o processo composto C

(Alencar-Neto, 2008; Frery et al., 2008).

Definio 36 (Processo pontual compostoC ). Objetivandomodelar as possveis situaes de

deposio de sensores a uma Rede de Sensores sem Fios, o processo composto C (n,), onde

denomina-se coeficiente de atratividade, implementado como segue, numa rea A R2.

Independente: processo pontual Binomial definido na regio A, na forma B [n,A].

Atrativo: composio de dois processos de Poisson, um com intensidade sobre uma rea

alvo A A e outro com intensidade , sobre a rea A\A, na forma S[n,].


(a) r = 0,01 (b) r = 0,05

(c) r = 0,10 (d) r = 0,11

Figura 3.5: Exemplos de um processo pontual de SSI com n = 100 e T = 1.000

Repulsivo: processo pontual SSI com raio de inibio rmax = n1/2, na forma SSI[n,rmax,A].

Regular: situao de repulso extrema, quando =.

Assim, este processo ser definido como

C (n,)=

SSI (n,rmax(1e)), se < 0

B(n), se 0 1S(n,), se > 1.

(3.1)

Na figura 3.6 pode-se observar exemplos do processo composto C.

Dado que para se espalhar sensores sobre grandes regies omeiomais comum o uso de

avies, os quais depem os ns sensores, modela-se este procedimento atravs do processo

C . Sob um plano de voo de altura constante, os sensores so depositados gradativamente,


num processo repulsivo (figura 3.6a). Caso sejam lanados muitos sensores de uma nica

vez, ns tendem a se aglomerar numa parte da regio, conforme um processo atrativo (fi-

guras 3.6c e 3.6d). Quando no h controle a deposio e esta se d de forma totalmente

aleatria, caracteriza-se um processo independente (figura 3.6b).

(a) =10: processo repulsivo (b) = 0: processo independente

(c) = 10: processo atrativo (d) = 50: processo fortemente atrativo

Figura 3.6: Exemplos do processo compostoC com n = 100

Este processo composto C ser um caso particular de um processo mais complexo, o

M2P2. Seguem as definies necessrias, extradas do trabalho de Ramos et al. (2010).

Definio 37 (Multilevel Marked Point Process). O processo M2P2(n,,m,rc ,ri ) representa

diversas possibilidades de deposio de sensores, onde n representa a quantidade de sensores e

o coeficiente de atratividade, m a quantidade de H-sensors (um grupo pequeno de sensores

com quantidade menor que a metade do total), rc o raio mximo de comunicao dentre os

L-sensors (sensores alm dos H-sensors), ri o raio de inibio dentre os H-sensors. Seja um

nmero pequeno m > 1 de H-Sensors num grupo n >m de L-Sensors num crculo de raio


rc > 0 centrado em cada H-Sensor. Os H-Sensors so depostos e em seguida os L-Sensors sodepostos prximos aosH-Sensors. Seja um processo pontual de Poisson de funo de inten-

sidade

(x, y)={ se d((x, y), (hxi ,hyi )) rc ,1 i m,1 caso contrrio,

onde d uma medida de distncia (neste trabalho, a euclidiana), {(hx1 ,hy1), . . . , (hxm ,hym )}

so as coordenadas dos H-Sensors e rc o raio mximo de comunicao dos L-Sensors.

Denote-se este processo por (n m,,rc ,h). O processo M2P2 um processo composto dem amostras de H(m,ri ), osH-Sensors, e nm amostras de(nm,,rc ,h), os L-Sensors. Oprocesso corresponde as seguintes configuraes de :

=1 processo totalmente binomial,= 0 processo repulsivo para osH-Sensors e binomial para os L-Sensors,

> 0 processo repulsivo para osH-Sensors e atrativo em torno dosH-Sensors para os L-Sensors.

(3.2)

Exemplos dessas situaes podem ser observados na figura 3.7.

3.1.3 Reconstruo do sinal

O sinal sera reconstrudo utilizando os algoritmos de kriging definidos nas sees 2.4.1 e

2.4.2 alm de algumas variantes. So estas:

kriging simples commdia constante

kriging simples commdia computada atravs de mnimos quadrados ordinrios

kriging simples commdia computada por mnimos quadrados generalizados

kriging ordinrio

kriging bayesiano

kriging bayesianomodificado (mdia computada pormnimos quadrados generaliza-

dos).

Uma vez com os campos devidamente reconstrudos, utilizar-se-o os valores compu-

tados pelas funes de kriging dos parmetros e para reconstruir os campos gaussia-

nos com a mesma funo que os gerou na primeira etapa do processo. Esse processo est

representado no diagrama da figura 3.8. Da natureza (N ) representa-se numericamente

um fenmeno de interesse (F representado em V ). Desse fenmeno coletam-se 50 valores

(R50) em pontos correspondentes s localizaes de sensores depostos (S), nos quais por


(a) =1

(b) = 0 (c) = 5

(d) = 15 (e) = 30

Figura 3.7: Exemplos do processoM2P2, com raio de comunicao 20, raio de sensoriamento5 e 6H-Sensors, para 100 sensores, variando o valor de , onde cadaM denota um L-sensor e umH-sensor

3.2. IMPLEMENTAONA PLATAFORMA R 35

um algoritmo de agrupamento () sero compostos 6 grupos, totalizando 6 valores de m-

dia aritmtica de cada grupo (R6). Com esses valores reconstri-se o sinal de origem com a

computao dos parmetros dos campos gaussianos do sinal de origem ( e , representa-

dos por ). A partir desses valores reconstrem-se os valores numricos do campo gaussiano

de origem (R100100).

NF R100100 S R50 R6 R100100

Figura 3.8: Diagrama ilustrativo da reconstruo dos campos gaussianos com base nos valo-res inferidos aos parmetros e pelos algoritmos de kriging

3.1.4 Validao domodelo

O modelo ser validado atravs do Mtodo de Monte Carlo (Metropolis & Ulam, 1949;

Murray, 1953; Robert & Casella, 1999), que consiste na repetio exaustiva do procedimento

utilizando dados diferentes, porm provenientes do mesmo processo. Para aferir a quali-

dade dos algoritmos,utilizam-se trsmtricas de qualidade: o vis (definio 39), a varincia

(definio 16) e o Erro Quadrtico Mdio (definio 40).

Definio 38 (Estimador). Constitui uma funo (ou sistemas de equaes) definida para

estimar o valor de um ou mais parmetros de uma distribuio D com base nas ocorrncias

de uma varivel aleatria X que siga a distribuio D.

Definio 39 (Vis). O vis do estimador , denotado B[], a diferena entre o valor espe-

rado do estimador e o verdadeiro valor do parmetro: B[]=E[].

Um estimador cujo vis seja igual a zero e dito no viesado.

Definio 40 (Erro Quadrtico Mdio EQM). Uma medida que leve em considerao no

apenas o quanto o valor estimado se distancia do valor verdadeiro como tambm avalie a

varinca dos valores estimados de grande importancia na avaliao de estimadores. Para

tal, o Erro Quadrtico Mdio define-se como EQM() = B2[]+Var(). Para um estimadorno viesado, o EQM reduz-se varincia do estimador.

3.2 Implementao na plataforma R

Diversos so os trabalhos que trazem tona a problemtica da falta de preciso numrica em

programas cientficos. Dentre diversos outros, podemos citar os trabalhos de Almiron et al.

(2009, 2010); Altman &McDonald (2001); Bustos & Frery (2006); Kennedy & Gentle (1980);


Callaert (2003); Altman et al. (2007); Oliveira & Stewart (2006), que no s avaliam o erro de

plataformas numricas como apresentam diversos erros que lhes so recorrentes, inclusive

trabalhos como o de Andel & Yasinac (2006), que avalia imprecises em simuladores de Re-

des de Sensores sem Fios. Sem a certeza de que os resultados so realistas, uma anlise

torna-se invivel.

R (R Development Core Team, 2009) uma linguagem e um ambiente de computao

funcional com um vasto ferramental de suporte estatstica computacional. um pro-

jeto da GNU (http://www.gnu.org) sob a licensa GPL (Michaelson, 2004; Ueda, 2005), fa-zendo parte dos programas de cdigo aberto denominados FLOSS (Free/Libre Open Source

Software). A qualidade de suas propriedades numricas pode ser aferida no trabalho de

Almiron et al. (2009).

Em seus repositrios oficiais (http://cran.r-project.org/mirrors.html) possvelencontrar uma vasta quantidade de pacotes que possibilitam incluir novas funes.

A base inicial das ferramentas de geoestatstica utilizadas nesse trabalho provm do pa-

cote geoR (Ribeiro Jr. & Diggle, 2001) que implementa os algoritmos de kriging simples, or-

dinrio e bayesiano. Uma nova verso do algorito de kriging bayesiano tambm proposta

modificando o j existente para que a mdia seja computada por mnimos quadrados gene-

ralizados, levando em conta os parmetros de covarincia, e que seja mantida fixa (no ser

ocorrncia de uma varivel aleatria, conforme definido na seo 2.4.2).

Para a implementao do algoritmo de agrupamento SKATER utiliza-se o pacote igraph

(Csardi & Nepusz, 2006), que implementa diversas operaes em grafos, alm de uma con-

veniente estrutura de dados para armazenamento dos grafos.

Os dados do sinal de origemprovm de funes para gerar campos aleatrios gaussianos

do pacote RandomFields (Schlather, 2009) e o ferramental para uso de processos pontuais

implementado pelo pacote spatstat (Baddeley & Turner, 2005).

A implementao do processo composto M2P2 a provida por Ramos et al. (2010).

O sistema de simulaes, ento, efetua as etapas enuciadas abaixo, com elementos refe-

renciados do diagrama da figura 2.8.

Gerao do sinal de origem: gera-se um campo aleatrio gaussiano (V ).

Deposio dos sensores: os sensores so depostos (S).

Agrupamento dos sensores: executa-se um algoritmo de agrupamento ().

Amostragem: os dados so coletados na forma (x, y), onde x denota o posicionamento ge-

ogrfico e y uma ocorrncia da varivel aleatria Y , que representa os dados amos-

trados no ponto x (V ). Ao se utilizar um algoritmo de agrupamento, cada clusterhead

efetua uma fuso dos dados de seu cluster e os valores coletados seguem com o posi-

cinamento geogrfico do clusterhead; apenas a informao fundida transmitida, da

mesma forma utilizada por Nordio et al. (2010).


Reconstruo do sinal: o sinal reconstrudo por um algoritmo de kriging (F ).

Para que os resultados sejam os mais realistas o possvel, so analisados sensores de-

postos atravs do processo M2P2 com coeficiente de atratividade 1, 0, 5 e 30. Em cadacampo gaussiano os sensores so depostos em suas cinco configuraes; em cada uma das

configuraes executam-se os dois algoritmos de agrupamento (sees 2.5.1 e 2.5.2), alm

de uma verso sem considerar agrupamentos; executam-se os trs algoritmos de kriging

(sees 2.4.1 e 2.4.2); no algoritmo de kriging simples efetua-se a mdia informada, com-

putada por mnimos quadrados ordinrios e computada por mnimos quadrados generali-

zados, considerando os valores de covarincia inferidos; no kriging bayesiano efetua-se o

algoritmo em sua forma tradicional, com mdia informada e com mdia computada por

mnimos quadrados generalizados consedirando os valores de covarincia inferidos. O di-

agrama da figura 3.9 ilustra o modo como as simulaes se processam, considerando que

cada transio (representa pelas setas) deve contemplar todos os parmetros.

Figura 3.9: Diagrama ilustrativo do sistema de simulaes

3.3. AMBIENTE DE EXECUO 38

3.3 Ambiente de execuo

A execuo das simulaes demanda grande poder computacional. Para tornar vivel a exe-

cuo de um estudo Monte Carlo com as variveis supracitadas utiliza-se de um ambiente

de computao de alto desempenho.

O ambiente em questo o cluster de computadores integrado GradeBR-UFAL, inte-

grado Rede Galileu (integrao dentre supercomputacores de quatro instituies: UFAL,

UFRJ, PUC-Rio e USP) do Laboratrio de Computao Cientfica e Visualizao da Uni-

versidade Federal de Alagoas. Este cluster composto de aproximadamente 170 ns com

dois processadores, cada um destes com quatro ncleos de processamento Intel Nehalem

(Intel Corporation, 2008), e 24GB de memria RAM. Entretanto o cluster ainda se encontra

em fase de implantao, no havendo disponibilidade de grande parte de seus ns, nem de

grades perodos para computaes.

O sistema de paralelizao das simulaes foi desenvolvido em linguagem C (ver c-

digo 3.1), utilizando a interface de paralelizao MPI (Walker & Dongarra, 1994). A imple-

mentao desta interface a OpenMPI (Gabriel et al., 2004), portvel diversas plataformas

(GNU Linux,MacOS,MicrosoftWindows, BSD e diversosmodelos baseados emUnix). O sis-

tema operacional utilizado o GNU Linux CentOS (http://centos.org) verso 5.4, kernelverso 2.6.18-164.el5 compilado para x86_64 (arquitetura amd64). O compilador utilizado

o Intel Compiler verso 11 (http://software.intel.com/en-us/intel-compilers).

1 cont

3.4. RESULTADOS ESPERADOS 39

20 Se rank = 021 {22 Se cont >= Total de arquivos23 incompleto

IVAnlise dos resultados

Will Frank Harrell or someone else please explain to me a real application in which this is

not fast enough?

Brian D. Ripley

R-devel (dezembro de 2004)

UMA vez comos dados da simulaomodelada no captulo 3, procedeu-se a anlise esta-tstica. Como as simualaes foram efetuadas atravs do mtodo de Monte Carlo porFora Bruta (Metropolis & Ulam, 1949; Murray, 1953; Robert & Casella, 1999), analisaram-se

o vis, a varincia e o erro quadrtico mdio dos estimadores.

Um aspecto importante na contruo desse processo a defino da ferramenta utili-

zada para a simulao. Como j apresentado na seo 3.2, a plataforma adotada foi o R

(R Development Core Team, 2009), devido a suas boas propriedades numricas. O uso de

outras plataformas foi avaliado, especifiamente plataformas de planilhas eletrnicas.

4.1 Implementao de simulaesMonte Carlo na literatura

A literatura sobre simulaes de Monte Carlo extremamente vasta. Uma busca simples

no ISI Web of Knowledge/Web of Science com a chave monte carlo retorna mais de 100.000

resultados.

Encontram-se disponveis diversos estudos que implementam simulaes Monte Carlo

utilizando planilhas eletrnicas. Dentre diversos outros, pode-se citar trabalhos, como o

de Li & Low (2010), que apresenta uma nova metodologia para anlise de riscos na sade

pblica; Tatone & Grasselli (2010) com uma modelagem probabilstica para o tombamento

de blocos com implementao baseada em planilhas eletrnicas; Schilstra &Martin (2009)

40

4.2. CRITRIOS PARA PESQUISA REPRODUZVEL 41

afirma que resultados interessantes de aplicaes simples sempre podem ser obtidos por si-

mulao deMonteCarlo emplanilhas eletrnicas; Rivard et al. (2009) efetua anlises de ben-

chmark para um equipamento de braquiterapia; Oscar (2009) modela a vida e crescimento

da salmonela.

Um maior destaque se d a trabalhos com grande nmero de citaes, como o de

Thompson et al. (1992), que extende modelagens da anlise de riscos na sade pblica;

Lindqvist & Westoo (2000) modelam uma avaliao de riscos ecotoxicolgicos em bacias;

e o de Vose (1998), que apresenta mtodos para anlise da contaminao de gneros ali-

mentcios. Esses trs ltimos trabalhos possuem mais de 40 citaes no ISI Web of Kno-

wledge/Web of Science, sendo os atualmentemais citados em uma busca com a chave spre-

adsheet monte carlo.

O uso das planilhas eletrnicas bastante difundido devido a sua facilidade de uso,como

pode ser visto no stio da European Spreadheet Risks Interest Group (2010). Nele podem ser

encontrados diversos casos de uso bem como histrias de desastres por erros em planilhas.

Ao mesmo tempo h diversos artigos na literatura que criticam o uso de planilhas em

aplicaes estatsticas devido a problemas numricos que lhes so recorrentes (ao exem-

plo de, dentre diversos outros,McCullough, 2008a,b, 2004, 1999, 1998;McCullough & Heiser,

2008; McCullough &Wilson, 2005, 2002, 1999; Nash, 2008, 2006). Entretanto, no incio deste

trabalho apenas foram encontradas disponveis na literatura anlises doMicrosoft Excel at

a verso 2003 e GNU Gnumeric; nada foi encontrado sobre outras planilhas eletrnicas, a

exemplo do OpenOffice.org Calc, a mais difundida dentre a comuindade Open Source. Isso

motiva a uma sria avaliao das propriedades numricas das planilhas eletrnicas antes de

seu uso.

4.2 Critrios para pesquisa reproduzvel

Para que a pesquisa possa ser validada por outros pesquisadores, a mais importante de suas

caractersticas a reproducibilidade. S atravs da capacidade de reproduzir os experimen-

tos e verificar a consistncia dos dados se podem avaliar a corretude dos resultados e a per-

tinncia das concluses.

O modelo adotado para suprir esta propriedade est detalhado por Koenker & Zeileis

(2009), almde uma vasta quantidadede informaes disponibilizadaspor Vandewalle et al.

(2009). As principais caractersticas necessrias s experinciasMonte Carlo so:

independncia de plataforma de sistema operacional;

independncia de plataforma de hardware;

capacidade de reproduzir a sequncia de nmeros pseudoaleatrios;

boas propriedades numricas.

4.2. CRITRIOS PARA PESQUISA REPRODUZVEL 42

Efetuou-se esta anlise nas planilhas eletrnicas mais difundidas, cujo contedo deta-

lhado pode ser obtido no trabalho de Almiron et al. (2010). As plataformas avaliadas, cujas

verses e arquiteturas de sistema esto apresentadas na tabela 4.1, foram:

OpenOffice.org Calc (http://www.openoffice.org/product/calc.html)

Microsoft Excel (http://www.microsoft.com/Excel)

GNU Gnumeric (http://www.gnome.org/gnumeric)

NeoOffice NeoCalc (http://neowiki.neooffice.org/index.php/NeoCalc)

GNUOleo (http://www.gnu.org/software/oleo).

Plataforma Calc Excel Gnumeric NeoOffice OleoHardware OS 2.4.1 3.0.1 2007 2008 1.8.3 1.9.1 2.2.5 3.0 1.99.16

Windows ! ! ! !i386

Ubuntu ! ! ! !

amd64 Mac OS ! ! ! !

Tabela 4.1: Plataformas de planilhas eletrnicas avaliadas

Para avaliar os geradores de nmeros pseudoaleatrios, adotaram-se os princpios de

Ripley (1990, 1987), que diz que bons geradores de nmeros pseudoaleatrios devem prover

sequncias numricas com as seguintes propriedades:

1. devem seguir a distribuio uniforme;

2. vetores de dimenso moderada de variveis aleatrias diferentes, mas do mesmo ge-

rador, devem ser coletivamente independentes;

3. devem ser reproduzveis atravs de poucos parmetros simples de especificar (a se-

mente), independente do ambiente computacional (hardware, sistema operacional,

linguagem de programao),

4. devem ser produzidas rapidamente,

5. devem possuir longos perodos.

Apenas atravs destes parmetros, simulaes Monte Carlo j se tornam inviveis em

planilhas eletrnicas, visto que apenas numa delas h documentao e possibilidade de in-

formar a semente (Excel 2007). De acordo com sua documentao, o gerador de nmeros

pseudoaleatrios implementado seria o de Wichmann & Hill (1982), entretanto, seguindo

a mesma metodologia de McCullough (2008a), pde-se verificar que essa informao est

incorreta. O gerador tambm no corresponde a nova verso deste gerador proposta por

4.3. DADOS OBTIDOS COM A SIMULAO 43

Calc Excel 2007 Excel 2008 Gnumeric NeoOffice Oleo

Documentao N S-incorreta N S N NSemente N S N N N N

Tabela 4.2: Documentao e disponibilidade de informar a semente em geradores de nme-ros pseudoaleatrios de planilhas eletrnicas

Wichmann & Hill (2006). A situao dos geradores dessas planilhas est resumida na ta-

bela 4.2.

No ambiente adotado, o R, h diversos geradores de nmeros pseudoaleatrios imple-

mentados. O gerador atualmente padro e utilizado neste trabalho o Mersenne-Twistter

(Matsumoto & Nishimura, 1998), que possui todas as propriedades supracitadas, com um

perodo de 2199371.

4.3 Dados obtidos com a simulao

Os dados resultantes do ensaio Monte Carlo foram os campos gaussianos reconstrudos, o

valor dos parmetros e e o valor estimado para a mdia, nos casos em que esta no foi

informada.

Para garantir a fidelidade nos valores a serem comparados, uma vez com os parme-

tros estimados os campos gaussianos so reconstrudos atravs da mesma funo que os

gerou. O valor das mdias tambm utilizado na reconstruo e analisado isoladamente.

Essa ltima anlise se torna relevante uma vez que, excesso do kriging ordinrio que pos-

sui estimador prprio para a mdia, os algoritmos so flexveis no modo como a mdia

computada. Tanto ela pode ser informada como estimada por padro atravs de mnimos

quadrados generalizados. Essa operao pode ter custo computacional invivel sistemas

de tempo real.

4.4 Anlise da qualidade do sinal reconstrudo

Conforme apontado por Diggle & Ribeiro Jr. (2007), o modelo de correlaoMatrn omais

utilizado por apresentar comportamento de interesse a diversos cenrios e possuir para-

metrizao no s de distanciamento () como tambm de suavizao de suas curvas ().

Assim sendo, as anlises deste trabalho consideram esse modelo de correlao.

4.4.1 Anlise do comportamento dos parmetros domodelo

Para a estimao dos parmetros e necessrio informar um ponto de partida para o

algoritmo. Em ambos os casos o valor informado foi 0,5, que, nos resultados onde se obteve

4.4. ANLISE DA QUALIDADE DO SINAL RECONSTRUDO 44

dados suficientes para anlise (100 replicaes), coincidiu com o valor real do parmetro .

O valor encontrado pelo estimador do parmetro foi este informado como partida (valor

correto). Os resultados das estimativas do parmetro encontram-se na tabela 4.3.

Kriging

Agrupamento Simples Ordinrio Bayesiano

Vis EQM Vis EQM Vis EQM

0,267981 11.26781 1,2875495 2.101374 0,07658597 0.007924418LEACH 6,98646 120,6482 8,78553 172,2060 2,135116 4,571751SKATER 3,47729 48,02378 274.238 81109 1,193697 8.668885

Tabela 4.3: Vis e EQM dos estimadores do parmetro para o valor real de = 5 e = 0,5

Nos cenrios avaliados, o modo como amdia foi informada no influenciou na estima-

tiva do parmetro . O kriging bayesiano apresentou resultado qualitativo muito superior

aos demais. O estimador utilizado pelo kriging ordinrio apresenta desvio muito grande, se

comparado aos outros algoritmos.

No caso do algoritmode agrupamento LEACH, a ordemdequalidade se repete, conforme

a tabela. As diferenas qualitativas no estimador de so bastante acentuadas, reforando

a qualidade superior nos dados providos pelo kriging bayesiano. Os resultados do algoritmo

de agrupamento SKATER so superiores qualitativamente aos do LEACH, mas consideravel-

mente inferiores aos sem agrupamento, excesso do kriging ordinrio, que apresenta uma

estimativa totalmente desviada do valor correto neste cenrio.

Dentre os trs tipos de kriging avaliados quanto a este estimador do parmetro , o kri-

ging bayesiano apresentou os melhores resultados. Estes resultados so melhores ainda ao

no se utilizar algoritmos de agrupamento. Para o caso com algoritmo de agrupamento,

o SKATER apresenta os melhores resultados, excesso do kriging ordinrio, que apresenta

umvis extremamente alto, indicandopossveis problemas do estimador como cenrio ava-

liado. Note-se que o comportamentodo estimador utilizadopelo kriging bayesiano sem uso

de algoritmo de agrupamento, mesmo sendo inferior aos demais, no apresenta vis muito

alto.

Como formade se obter umamedida unificadade qualidade,utiliza-se o ErroQuadrtico

Mdio (EQM ver definio 40). Neste, obtm-se uma conceituao que leva emconta o vis

e a varincia.

Em todos os casos o estimador utilizado pelo kriging bayesiano apresenta resultados

qualitativamentemuito superiores ao demais algoritmos. O destaque aindamaior quando

no se usa algoritmo de agrupamento, onde o EQM reduz-se para menos de 102. exces-

so dos resultados sem uso de algoritmo de agrupamento, onde o kriging ordinrio supera

os do kriging simples, este apresenta resultados superiores aos daquele. Os resultados do

algoritmo SKATER so superiores aos do algoritmo LEACH, mas bastante inferiores se com-


parados aos sem uso de algoritmo de agrupamento.

4.4.2 Anlise do campo gaussiano reconstrudo

A anlise dos campos gaussianos reconstrudos divide-se em duas fases. Na primeira,

analizam-se os dados de interpolao provenientes das funes de kriging;na outra, os cam-

pos so reconstrudos com base nas estimativas dos parmetros.

Amedida de qualidade adotada neste trabalho amesmausada porAlencar-Neto(2008):

o erro absoluto relativo, descrito como

= 1104

100i , j=1

g (i , j ) g (i , j )g (i , j ) , (4.1)

onde g representa o campo gaussiano original e g o campo gaussiano recostrudo.

Campos reconstrudos por kriging

A mdia dos erros absolutos relativos oriundos dos campos reconstrudos pelo processo de

kriging em cada um dos cenrios avaliados esto expostas na tabela 4.4.

Kriging Simples commdia: Sem cluster LEACH SKATER

Informada 1,767403e-06 1,677676e-06 2,518104e-06Mnimos Quadrados Ordinrios 1,660393e-06 1,484805e-06 2,296276e-06Mnimos Quadrados Generalizados 1,672886e-06 1,555376e-06 2,299960e-06

Kriging Ordinrio commdia:

Inferida 1,545347e-06 1,572371e-06 4,322422e-06

Kriging Bayesiano commdia:

Inferida 1,565611e-06 2,567227e-06 3,256432e-06Mnimos Quadrados Generalizados 1,565611e-06 2,567227e-06 3,256432e-06

Tabela 4.4: Mdia dos erros absolutos relativos dos campos reconstrudos pelo processo dekriging com = 0,5 e = 5

Os trs tipos de kriging apresentam resultados de prximos. Sem o uso de algoritmo

de agrupamento e para o algoritmo LEACH, o kriging ordinrio apresenta os melhores re-

sultados qualitativos no sinal reconstrudo. Para o algoritmo SKATER, o kriging bayesiano

apresenta os melhores resultados.

Concordantemente aos resultados anteriores, os menores valores de de so obtidos

sem o uso de algoritmo de agrupamento. Dentre os dois algoritmos avaliados, o LEACH

apresenta os melhores resultados.


Campos reconstrudos a partir dos parmetros estimados

Comos valores dos parmetros estimados, o campo gaussianooriginal foi reconstrudo atra-

vs damesma funo que o gerou, conforme o algoritmoapresentadono cdigo 4.1. Se g a

funo que gera o campo gaussiano com os valores reais do parmetro (), a mesma funo

com os parmetros estimados () constituir a funo g , estimador de g ().

Para g computam-se asmesmas anlises efetuadas nos parmetros (vis, varincia e erro

quadrticomdio).

1 Para cada simulacao efetuada2 {3 campo

4.5. ANLISE DO TEMPONECESSRIO RECONSTRUODO SINAL 47

Kriging Simples commdia: Sem cluster LEACH SKATER

Mnimos Quadrados Ordinrios 4,750628e-08 1,546162e-06 8,08544e-07Mnimos Quadrados Generalizados 2,46977e-07 1,546162e-06 7,73929e-07

Kriging Ordinrio commdia:

Inferida 1,671397e-07 1,857702e-06 8,08544e-07

Kriging Bayesiano commdia:

Inferida 1,671397e-07 3,302198e-06 1,872057e-07Mnimos Quadrados Generalizados 1,671397e-07 3.302198e-06 1.375265e-06

Tabela 4.6: Mdia dos erros absolutos relativos dos campos reconstrudos pelos parmetrosinferidos para = 0,5 e = 5 e mdia = 100

4.5 Anlise do tempo necessrio reconstruo do sinal

Redes de Sensores sem Fios so utiliadas nos mais diversos cenrios e, dentre diversos ou-

tros, muitos envolvemdeteco de riscos iminentes, bem como incndios em florestas, con-

centrao de gases txicos (Akyildiz et al., 2002; Sha et al., 2006; Lloret et al., 2009). Nessas

aplicaes, o tempo necessrio reconstru do sinal crucial, dado que a funo do sis-

tema o combate ao fator, que em pouco tempo se propaga atingindo propores cada vez

maiores.

Assim sendo, no basta que a tcnica utilizada para a reconstruo do sinal seja efici-

ente na qualidade dos dados, mas que seja eficaz no tempo de reconstruo. Este problema

est referenciado em diversos trabalhos, dentre os quais, os de Sha et al. (2006); Lloret et al.

(2009); Fierens (2009) e Tsow et al. (2009).

importante ressaltar que isso se d a depender dos recursos computacionais. Mesmo

que atualmente no haja alternativa disponvel, possvel que em alguns anos, com o au-

mento do poder computacional disponvel, esse tpico seja preterido.

4.6 Consideraes acerca dos dados obtidos

Em virtude da alta demanda computacional requerida pelo processo de kriging bayesiano

e do fato do cluster da GradeBR-UFAL no ter sido entregue, foram realizadas simulaes

de poucos cenrios. Entretanto, encontra-se em andamento a simulao de diversos outros

cenrios que faro parte de um trabalho resultante desta pesquisa, a ser publicado.

VResultados e discusses

It was simple, but you know, its always simple when youve done it.

Simone Gabbriellini

R-help (agosto de 2005)

A anlise dos dados do captulo 4 permitiu observar amaior qualidade dos dados geradospelo algoritmo de kriging bayesiano na maioria dos cenrios avaliados. Entretantoele no apresenta bom comportamento com o algoritmo LEACH. Neste cenrio o kriging

simples apresentou os melhores resultados.

Algo a se considerar que nem sempre sua utilizao vivel em decorrncia de sua

necessidade de alto poder computacional (ver seo 4.5). exemplo, sistemas de tempo real

no so suscetveis a computaes de longos perodos de tempo; necessrio que a reao

seja imediata solicitao.

O sinal reconstrudo diretamento pelos algoritmosde kriging apresentamaior qualidade

que os gerados pela mesma funo utilizada para a construo dos campo gaussianos de

amostras, informando as estimativas dos parmetros e . Esta ltima situao, excesso

da emque se utiliza o kriging bayesiano, necessita demenor tempo de computao,uma vez

que a interpolao no necessita ser efetuada, basta estimar os parmetros e inform-los

funo que gera campos gaussianos.

O kriging que necessita de menor tempo para estimao dos parmetros e reconstruo

do campo gaussiano o ordinrio. Os parmetros e estimados no apresentam resul-

tados superiores ao kriging simples, mas os resultados da reconstruo dos campos gaussi-

anos superior ao kriging simples em todos os cenrios avaliados que no o do algoritmo

LEACH.

O kriging ordinrio, ento, apresenta os melhores resultados na relao qualidade dos

parmetros estimados / tempo de execuo, uma vez que no se conseguiu obter execu-

48

4.6. CONSIDERAES ACERCA DOS DADOS OBTIDOS 49

o de reconstruo por kriging bayesiano em menos de uma hora e trinta minutos, numa

das estaes especificadas no capitulo 3. importante ainda considerar que os exemplos

simulados neste trabalho possuam apenas 100 100 pontos; num caso real esse nmeropode ser de escalas bem maiores, o que pode elevar muito o tempo de execuo. Mesmo

os resultados do kriging bayesiano sendo em geral superiores qualitativemente, ele s pode

ser utilizado quando houver grande poder computacional e/ou no houver necessidade de

resultados rpidos.

Para o kriging bayesiano foi avaliada uma variante proposta neste trabalho, que consiste

na incluso da informao a priori do parmetro de mdia, transformada numa constante

para o sistema de reconstruo. Essa abordagem possibilitou reduo no tempo necessrio

de processamento, uma vez que a computao da mdia deixa de ser por inferncia baye-

siana e passa a ser efetuada por mnimos quadrados ge

Documents

Tese de Mestrado Bruno