Agregação e Predição de Dados Em Rede com Precisão Ajustável no Processamento de Consultas em Redes de Sensores Sem Fio

Agregação e Predição de Dados Em Rede com Precisão Ajustável no Processamento de Consultas em Redes de Sensores Sem Fio Tales Benigno Matos1, Ângelo Brayner1, J. E. Bessa Maia2 Mestrado em Informática Aplicada – Universidade de Fortaleza (UNIFOR) Departamento de Estatística e Computação – Universidade Estadual do Ceará 1

2

{rtales,brayner,jmaia}@unifor.br

Resumo. Muitas pesquisas em redes de sensores sem fio (RSSF) têm sido desenvolvidas nos últimos anos, com foco na economia de energia dos nós sensores. Para alcançar este objetivo, tais pesquisas utilizam como estratégia a redução de dados enviados na rede. Neste trabalho, é proposta uma estratégia eficiente de agregação e predição de dados em RSSF, com este objetivo, aumentando a vida útil da RSSF. Além do uso da agregação em rede, a proposta apresentada neste artigo introduz o conceito de predição em rede, realizada no processamento de consultas sobre RSSFs. A predição proposta utiliza um modelo de regressão linear, com base nos dados coletados de um único sensor ou com base nos dados de um subconjunto de sensores. Ela é executada de forma distribuída nos diversos sensores de uma RSSF. Os resultados experimentais mostram que a estratégia proposta pode reduzir significativamente o consumo de energia em RSSFs. Abstract. Over the past few years, many research works in Wireless Sensor Networks (WSN) have been focusing on node power saving. In order to achieve this goal, the amount of data sent over the node network is usually reduced. In this work, we propose an efficient strategy that aggregates and predicts data in WSN, aiming to reduce the data volume sent over the network and thus maximizing the network lifetime. Besides the widely used in-network aggregation strategy, this work presents the use of innetwork prediction, based on query processing on the network data. Our prediction strategy works with a linear regression model, using data acquired from one or several sensor nodes. It is implemented in various sensor nodes distributed in a WSN. Experimental results show that our strategy is able to significantly reduce power consumption in WSN.

1. Introdução O interesse no desenvolvimento de sistemas para coletar dados via Redes de Sensores sem Fio (RSSF) tem aumentado muito nos últimos anos (e.g., TinyDB [Madden et al. 2008], Cougar [Yao et al. 2002] e directed diffusion [Bonnet et al. 2001]). Implementar RSSFs pode envolver técnicas que habilitam os dispositivos a tomarem decisões baseadas em seu ambiente local. As RSSFs podem ser utilizadas em aplicações dos mais diversos tipos, como o monitoramento de animais em seu habitat natural [Polastre et al. 2002], o acompanhamento de informações meteorológicas e ambientais, aplicações militares e comerciais, monitoramento industrial e controle de processos [Adler et al. 2005], bem como aplicações científicas diversas. Atualmente, um sensor é um equipamento dotado de uma memória de capacidade bastante limitada, uma unidade de processamento de baixo desempenho, uma unidade de sensoriamento para coletar dados do ambiente ou medir fenômenos físicos, um transmissor/receptor de curto alcance e uma bateria de baixa autonomia. O sensor tem

como premissa, a capacidade de operar independente da intervenção humana. Para economizar energia, um nó sensor deve ficar em um estado de latência (adormecido), despertando apenas para coletar, transmitir ou receber dados. O ponto crítico em Redes de Sensores Sem Fio refere-se ao consumo de energia dos nós sensores. O maior consumo de energia em um nó sensor ocorre na transmissão ou recepção de dados [Madden et al. 2003]. Em [Tilak et al. 2002] é mostrado que a execução de 3000 instruções gastam a mesma quantidade de energia que enviar 1 bit a 100m via rádio. Muitas técnicas com foco em restrições de energia [Madden et al. 2002, Yao et al. 2002, Deligiannakis et al. 2006, Wun et al. 2007, Patt-Shamir 2007] têm sido propostas para o processamento de consultas sobre RSSFs. A utilização de operadores de agregação em rede [Brayner et al. 2006, Madden et al. 2002, Wun et al. 2007, Patt-Shamir 2007] tem se tornado uma importante estratégia para redução do volume de dados transmitidos em uma dada RSSF. Como mencionado, anteriormente, tal redução implica em uma economia de uso de bateria por parte de sensores, aumentando, desta forma, a vida útil de uma RSSF. A principal contribuição deste trabalho é a extensão do mecanismo de agregação de dados proposto em [Brayner et al. 2006, Brayner et al. 2007] para incorporar uma função de predição de dados, baseada na regressão linear, aplicada a dados anteriores. Tal extensão diminui a necessidade de transmissão de dados, diminuindo com isso o consumo de energia em uma RSSF. O algoritmo proposto é capaz de realizar predições dos dados de um sensor a partir de seus próprios dados, ou a partir dos dados de outro sensor, ou ainda a partir dos dados de um subconjunto de sensores. Isto é possível, pois os coeficientes da regressão linear estão distribuídos nos sensores de uma RSSF, como está detalhado na seção 4. A estratégia de predição proposta traz ainda a propriedade de precisão ajustável. A idéia é permitir ao usuário definir uma diferença tolerável entre o valor coletado e o valor predito pelo mecanismo proposto. Com o parâmetro diferença tolerável, os nós sensores só transmitiriam dados coletados com valores maiores do que a soma entre o parâmetro diferença tolerável e o valor resultante do processo de predição. O parâmetro diferença tolerável também é utilizado para definir o momento de recalcular os coeficientes da regressão linear, pois, quando um valor coletado é maior do que a soma entre a diferença tolerável e o valor resultante do processo de predição, torna-se necessário o recálculo destes coeficientes. Como decisão de projeto, o parâmetro diferença tolerável deve ser definido mediante uma cláusula denominada threshold, adicionada à linguagem de consulta SNQL (Sensor Network Query Language) [Brayner et al. 2007], que também é utilizada neste trabalho. É importante o fato de que o valor da cláusula threshold determina a precisão do resultado de uma consulta. São apresentados resultados experimentais da estratégia proposta, utilizando-se de dados reais e sintéticos. Tais resultados comprovam que a estratégia proposta reduz o consumo de energia, aumentando, conseqüentemente a vida útil de uma RSSF, como está demonstrado na seção 5 deste artigo. As demais seções deste artigo estão organizadas como descrito a seguir. A seção 2 analisa e discute os trabalhos relacionados mais relevantes. Em seguida, a seção 3 apresenta o modelo de RSSF adotado neste trabalho, bem como uma breve descrição da

linguagem de consultas SNQL. A seção 4 traz o modelo de regressão linear utilizado para realizar a predição dos dados. A seção 5 apresenta os resultados obtidos através de simulações com a predição, em comparação com outras estratégias. Finalmente, a seção 6 conclui este trabalho.

2. Trabalhos Relacionados A estratégia de agregação e predição de dados proposta neste trabalho utiliza como ponto de partida o trabalho apresentado inicialmente em [Brayner et al. 2006] e estendido em [Brayner et al. 2007], onde é definido o operador ADAGA (ADaptive AGregation Algorithm for sensor networks). Ele é um operador físico de agregação de dados para o processamento de consultas em RSSF, que se caracteriza por executar a agregação de forma distribuída em vários sensores espalhados em uma RSSF. Outra propriedade importante encontrada neste operador é sua capacidade em adaptar seu comportamento de acordo com o uso de memória e de energia. Para gerar resultados mais precisos, ele faz uso de uma estratégia de predição de dados que deixaram de ser coletados, por falta de memória disponível. Vale destacar que no cenário do ADAGA, resultados precisos representam resultados que seriam obtidos, caso não houvesse nenhuma restrição de memória e bateria em todos os nós sensores participantes na execução de uma dada consulta. Para uma discussão mais detalhada sobre o ADAGA, recomenda-se a leitura de [Brayner et al. 2006]. Abordagens similares ao ADAGA são apresentadas nos sistemas TAG [Madden et al. 2002], TinyDB [Madden et al. 2008] e Cougar [Yao et al. 2002]. Para reduzir o consumo de energia da rede de sensores sem fio, TAG e COUGAR examinaram as propriedades das consultas de agregação e propuseram uma topologia de árvore para a RSSF, onde os nós da rede formam uma árvore de agregação, na qual os nós pais agregam os valores recebidos de seus filhos e propagam o resultado para seus próprios pais. Isto permite a agregação de dados em todos os níveis da árvore para agregações algébrica (Média) e distributiva (Max, Min, Count e Sum). Desta forma, estas estratégias também utilizam a agregação em rede. O projeto TAG também apresenta características como disseminação de consultas, sincronização de sensores e técnicas para otimização de consulta, baseadas nas características das funções de agregação utilizadas. Características semelhantes também são sugeridas para o TinyDB, mas sua ênfase está na redução do consumo de energia pela determinação de taxas de amostragem apropriadas para cada origem de dados. As propostas de agregação em rede apresentadas pelo TinyDB, TAG e Cougar não trabalham com a idéia de predição de dados para gerar resultados com maior precisão, tão pouco introduzem a propriedade de adaptabilidade, que permitiria àqueles operadores de agregação adaptar seu funcionamento de acordo com a quantidade de memória e energia disponíveis. Em [Deligiannakis et al. 2006] é proposta uma estratégia de agregação em rede que suporta consultas com valores aproximados, para reduzir a troca de mensagens entre os nós da rede. Esta estratégia implementa a agregação em rede através do conceito de árvore de agregação. Desta forma, esta estratégia reduz a troca de mensagens de nós irmãos (na árvore de agregação), quando seus dados coletados estiverem dentro de uma margem de erro, considerando os dados coletados anteriormente. Vale destacar que na estratégia em [Deligiannakis et al. 2006] não existe a predição de dados futuros. Além disso, esta estratégia de agregação de dados em rede não faz o ajuste dinâmico da consulta submetida à rede, em função do consumo de energia pelos nós sensores.

Além da agregação, a predição vem sendo bastante utilizada como forma de reduzir o envio de dados pelos nós sensores, aumentando bastante o tempo de vida da rede. Vários métodos de predição que fazem uso da regressão linear [Kumar et al. 2004, Emekci et al. 2003, Desnoyers et al. 2005, Deshpande et al. 2006] vêm sendo utilizados, em RSSF. São estratégias que utilizam correlação temporal e espacial [Kumar et al. 2004], características do ambiente e do fenômeno que está sendo sensoriado, além da redundância nas medições obtidas [Kumar et al. 2004, Emekci et al. 2003, Desnoyers et al. 2005, Deshpande et al. 2006]. Vale destacar que a estratégia proposta neste artigo também faz uso de regressão linear para predizer dados futuros. Contudo, diferencia-se das estratégias anteriores, principalmente, pelo fato da nossa predição ser realizada sobre dados agregados e também por executar a predição de forma distribuída nos diversos nós sensores de uma RSSF.

3. Rede de Sensores Sem Fio Uma rede de sensores sem fio (RSSF) é uma rede composta por um grande número de nós sensores, posicionados aleatoriamente em uma região geográfica, com o objetivo de coletar dados do ambiente relativos à detecção ou medição de algum fenômeno físico. Sensores podem realizar vários tipos de sensoriamento, normalmente com baixa freqüência de amostragem, como por exemplo: temperatura, pressão, umidade, luminosidade, níveis de ruído, medidas de posição, velocidade e aceleração de objetos, concentração de substâncias, entre outros. A figura 1 ilustra o modelo de RSSF pressuposto neste trabalho. Neste modelo, uma RSSF pode ser composta por três tipos de nós sensores: (i) nós folha, que são nós sensores comuns, responsáveis pelo sensoriamento e transmissão de dados coletados, podendo ser responsáveis também pela recepção e retransmissão de dados de outros sensores; (ii) nós sink, que representam sensores mais robustos do ponto de vista computacional, pois, além de possuírem as mesmas características dos nós folhas, são também responsáveis por atividades, como agregação e predição de dados coletados por grupos de nós folha, onde estes grupos podem ser vistos como sub-rede de sensores associados a um determinado nó sink, e; (iii) uma estação base, que se caracteriza por possuir maior capacidade de armazenamento de dados e por não apresentar restrição de bateria, nem de capacidade de processamento. Nós Folha – sensores comuns que formam aglomerados ou sub-redes ligadas a um nó Sink. São responsáveis pela coleta de dados do ambiente, podendo utilizar estratégias de agregação quando solicitado; Nós Sink – dispositivos de maior capacidade de processamento, com maior limite de energia e mais memória que o nó folha. Responsáveis pela predição dos dados, pelo repasse das consultas aos nós folha e pelo envio das informações coletadas pelos sensores à estação base; e Estação Base – computador ou dispositivo portátil (notebook, handheld, etc.), utilizado pelos usuários para injetar consultas na rede.

Figura 1. Topologia de RSSF assumida neste trabalho.

Vale destacar que na estratégia proposta para predição de dados, cada nó do tipo sink, utilizando-se de dados coletados no ambiente, é responsável por calcular os coeficientes da equação de regressão dos sensores associados à sua sub-rede.

O modelo de dados utilizado é o mesmo proposto em [Brayner et al. 2006]. Seu objetivo é permitir uma visão lógica sobre os fluxos de dados manipulados pelo sistema, fazendo com que os dados que trafegam na RSSF sejam interpretados como tuplas de um modelo relacional (relações virtuais). A vantagem deste modelo está na abstração do usuário em relação aos detalhes físicos da RSSF. Para especificar consultas declarativas em uma RSSF, usando o modelo proposto, é utilizada a linguagem de consulta SNQL [Brayner et al. 2007]. Ela possibilita a definição de diversos parâmetros de controle, como volume de dados injetados na rede e a precisão dos resultados. Na tabela 1, estão apresentadas as principais cláusulas DML (Data Manipulation Language) desta linguagem. Tabela 1. Cláusulas DML da SNQL. Cláusulas SELECT {} FROM {}

Especificações : Especifica um subconjunto dos atributos nas relações (grupos de sensores) de origem. Serão aceitas também funções de agregação conforme a definição na linguagem. : Especifica um ou mais grupos de sensores considerados.

[WHERE {}]

: Especifica um conjunto de predicados de seleção das tuplas a serem processadas.

[GROUP BY {} [HAVING {}]]

: Especifica um subconjunto de atributos nos quais as funções de agregação se basearão. : Especifica predicados, baseados nas funções de agregação, que filtrarão os resultados agregados.

TIME WINDOW | CONTINUOUS

: Define o intervalo de tempo do tempo de vida da consulta (e.g., 3600s). A cláusula CONTINUOUS denota que o tempo de vida da consulta é infinito. [DATA WINDOW] : Especifica um número exato de dados a ser coletado (linhas), determinando o tempo de vida da consulta. SEND INTERVAL : Especifica o intervalo de tempo entre dois envios consecutivos de pacotes pelos nós sensores (e.g., 120 s). SENSE INTERVAL : Especifica o intervalo entre duas coletas de dados pelos nós sensores (sensoriamento). [SCHEDULE [{datetime}] | CONTINUOUS]

: Define o número de vezes que a consulta será injetada no sistema.

A figura 2 apresenta um exemplo de consulta, para ilustrar a especificação de consultas sobre RSSFs através da SNQL. Considere uma consulta Q, que deverá retornar um resultado conforme os critérios descritos a seguir: • Descubra para cada sensor, a média de temperatura coletada por ele, no ambiente onde ele está inserido. Submeta a consulta uma vez, em 01-Feb-08 às 00:00:00. A execução deve durar 9x104 segundos. Dados devem ser coletados a cada 10 segundos e enviados à estação-base a cada 3x103 segundos. SELECT t.Sensor, avg(t.ValorColetado) FROM Temperature as t GROUP BY t.Sensor TIME WINDOW 90000 SEND INTERVAL 3000 SENSE INTERVAL 10 SCHEDULE 1 ‘01-Feb-08 00:00:00’

Figura 2 – Consulta Q emitida a partir da aplicação gerenciadora na estação base.

Os sensores e a estação base usam as cláusulas Time Window e Data Window para identificar o momento de parar a execução de uma consulta. O valor Continuous na cláusula Time Window especifica uma consulta contínua. A cláusula Sense Interval especifica o intervalo entre duas coletas de dados consecutivas. Quanto maior o valor para esta cláusula, menos dados serão coletados,

reduzindo a precisão da consulta. Já uma redução no valor desta cláusula implica mais coletas, mais processamento e mais dados sendo armazenados. Já a cláusula Send Interval precisa ser cuidadosamente definida na consulta, pois o seu valor impacta diretamente no uso de memória do sensor e no consumo de energia da rede. Para valores altos, haverá um acúmulo maior de dados pelo sensor o que pode gerar um estouro na capacidade de memória deste. Quanto ao consumo de energia, haverá menos transmissão de dados, economizando energia; no entanto, valores baixos para esta cláusula podem produzir maiores quantidades de pequenos pacotes, aumentando o tráfego na rede e, conseqüentemente, aumentando o consumo de energia pela rede. Sendo assim, os valores das cláusulas de Sense Interval e Send Interval influenciam diretamente no desempenho e no tempo de vida da rede [Brayner et al. 2006]. Vale destacar que o ADAGA pode ajustar dinamicamente os valores para as cláusulas de Send Interval e Sense Interval. Com o intuito de realizar predições para dados que suportam certa diferença entre o valor coletado e o valor da predição, adicionamos uma nova cláusula à linguagem SNQL (Tabela 2), denominada threshold, que indica a um nó sensor o limite de diferença entre o valor coletado e o valor estimado. O sensor não deve enviar dados até que o valor do threshold seja ultrapassado. Para tanto, é suficiente a utilização da seguinte fórmula: P≥100(Vc-Vp)/Vc, onde P representa o valor, em percentual, especificado na cláusula threshold, Vc corresponde ao valor coletado pelo nó sensor e Vp é o valor resultante do processo de predição (valor predito). Desta forma, a predição pode ser ajustável quanto ao threshold. Por exemplo, se o usuário definir a cláusula threshold com um valor de 5%, isto implicará uma consulta que aceita uma predição de dados com tolerância de 5% (diferença entre o valor coletado do ambiente e o valor da predição). Tabela 2. Cláusulas DML adicionada à SNQL. Cláusula THRESHOLD

Especificações < sndpercent >: Especifica a tolerância a erro da predição (e.g., 5%).

4. Predição dos dados As leituras de um sensor podem ser consideradas uma série temporal discreta, onde o tempo corresponde ao instante quando o valor do sensor foi coletado, as leituras do sensor são os valores e a faixa de tempo é determinada pelo tempo de duração da consulta. Para predizer as leituras futuras, torna-se necessário encontrar uma tendência nas séries temporais. Do ponto de vista da precisão dos dados, o ideal seria detectar o padrão de mudança exato dos valores coletados (lidos) dos sensores. Isto, no entanto, necessita de muitas amostras de dados e execução de algoritmos de análise fora da rede (off-line), já que consomem muitos recursos computacionais, ou seja, apresentam alto custo computacional. Neste sentido, a técnica de regressão linear foi escolhida como estratégia de predição, pelas seguintes razões:





é simples e de complexidade linear, propriedades desejáveis para algoritmos a serem executados em dispositivos computacionais, como nós sensores, com limitada capacidade computacional. Em nossa proposta, um nó sensor é provido com um modelo de predição (regressão linear) e os coeficientes da equação de regressão são calculados pelos nós do tipo sink; o modelo contém poucos parâmetros, consumindo, assim, menos banda de comunicação e memória. Isto ocorre porque cada nó sensor executa o modelo de




predição e, quando a predição para a leitura atual diverge além do threshold, novos coeficientes são calculados pelo sink e enviados ao sensor; e a precisão dos dados pode ser definida pelo usuário, por intermédio da cláusula de threshold da SNQL, e é garantida pelo modelo proposto de regressão linear.

No modelo de predição proposto neste artigo, a função de predição de um nó sensor é armazenada no próprio sensor. Na verdade, o que muda na equação de predição armazenada no diversos sensores de uma RSSF são os coeficientes da equação de regressão linear (veja seção 4.1). O cálculo destes coeficientes é feito por nós do tipo sink, com base nos valores coletados e enviados a estes pelos nós folha. A coleta e predição dos dados são realizadas como descrito a seguir. Cada nó do tipo sink de uma RSSF deverá armazenar todos os dados necessários para realizar o cálculo dos coeficientes da equação de regressão de sua sub-rede. Os coeficientes são recalculados sempre que chega uma nova informação do nó folha ou sempre que é atingido o limite da cláusula SendInterval. Cada coeficiente é então enviado ao nó folha correspondente e este não precisará enviar uma nova coleta enquanto a diferença entre o valor da predição e o valor coletado for menor do que um dado limite predefinido (threshold). Assim, cada sink gera os dados e os envia à estação base de acordo com os parâmetros da consulta. Vale destacar que, para uma dada quantidade de sensores da rede, cada sink divide estes sensores em três segmentos: dormindo (sleeping), ouvindo (listening) e enviando (sending). O objetivo do algoritmo de predição proposto é, então, o de reduzir o conjunto de sensores que enviam dados (sending), reduzindo, conseqüentemente, o consumo de energia de um nó sensor na RSSF. 4.1 Regressão Linear Na estratégia de predição proposta, é pressuposto que cada nó folha está pré-programado com a equação de regressão linear (fórmula da predição) e receberá os coeficientes que vêm do sink (responsável pelo sensor), sempre que a diferença entre o valor coletado e o valor estimado for maior do que o especificado na cláusula threshold (veja seção 3). É importante observar que, se um nó folha perder os coeficientes da predição, ele irá desprezar o threshold e receberá os valores dos coeficientes novamente quando enviar uma nova coleta ao sink. Por sua vez, a estação base deve possuir um banco de dados com todos os valores coletados e deverá armazenar também as predições que estão atualmente em vigor, pois, caso um sink perca seus dados, este poderá solicitá-los novamente à estação base. Para realizar a predição, consideramos a regressão linear simples, com a seguinte equação: Sˆ(t) = a + b * t O tempo t é a variável independente. Sˆ(t) representa o valor estimado de S(t) e é variável com t. O parâmetro a é o intercepto-t (valor de Sˆ(t) para t=0) e b é o coeficiente angular ou inclinação da reta. Observe que a e b são os coeficientes de regressão e podem ser calculados da seguinte forma:

b = ∑ i (t − t i)2 ∑i

(t − t )(S − S )

, onde t denota a média de t , e S denota a média de S1 , S 2 ,....,S n .

a = 1n (∑Si − b ∑ti ) = S − b t Cronologicamente, ao realizar a predição, cada nó sink segue os seguintes passos:

(i) o sink recebe os dados e calcula os coeficientes a e b; (ii) em seguida, cada nó sink envia os coeficientes para os sensores de sua região, que passam a comparar as leituras do ambiente com a predição, respeitando o limite de threshold. Lembre-se de que os nós sensores coletam dados a cada Sense Interval e enviam dados (apenas quando a diferença entre o valor coletado do ambiente e o valor da predição é maior do que o especificado na cláusula threshold) a cada Send Interval, durante um Time Interval. Todos estes parâmetros estão especificados na consulta (em SNQL) injetada na RSSF; e (iii) como cada sink fica responsável por uma sub-rede (região) de sensores (veja Figura 1), cada nó sink conhece os valores para os parâmetros Sense Interval e Send Interval, para uma dada consulta, executada nos sensores desta região. Desta forma, caso chegue algum valor enviado por um sensor ao nó sink, este usa o valor recebido e recalcula os coeficientes. Desta forma, a precisão da predição ajusta-se continuamente. Vale mencionar que sempre que um sensor fica sem enviar dados, ele permanece no estado de sleeping ou de listening, economizando energia, aumentando, dessa forma a vida útil da RSSF. Para ilustrar a eficiência da estratégia de predição proposta, considere a Figura 3. Nesse sentido, suponha que foi injetada uma consulta Q em uma RSSF, cujo objetivo é detectar a temperatura do ambiente, com coleta de dados a cada 5 segundos, pacotes (dados) sendo enviados por cada sensor (envolvido na consulta) a cada 20 segundos, durante 280 segundos. Caso a estratégia de predição não fosse empregada, cada sensor deveria enviar 14 pacotes. Na figura 3, estão representados dados reais de um sensor utilizados nos testes de avaliação da estratégia proposta (veja seção 5.1). Observe que, no caso deste sensor, são enviados apenas quatro pacotes, considerando um threshold de 5%. Este fato representa significativa economia de energia, pois o sensor observado não precisou enviar 71% dos pacotes. Na seção 5.1, está demonstrado que esta economia pode ocorrer para todos os sensores. Naturalmente, esta redução de consumo ocorrerá em magnitudes diferentes para os diversos sensores envolvidos em uma dada consulta injetada em uma RSSF, mas, no cômputo final, haverá uma real redução no consumo de energia da rede, o que representa aumento na vida útil de uma RSSF. Linha de Tempo(s): Temperatura (ºC): Predição (ºC):

20

40

60

80

100

120

140

160

180

200

220

240

260

|

|

|

|

|

|

|

|

|

|

|

|

|

280

|

15

15

14

15

16

16

17

16

16

16

16

17

17

17

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

16,17 16,17 16,12 16,17 16,22 16,22 16,28 16,22 16,22 16,22 16,22 16,28 16,28 16,28

Pacotes enviados por S: Pacotes da Predição*:

15

15

14

15

16,22 16,22 16,28 16,22 16,22 16,22 16,22 16,28 16,28 16,28 * Pacotes que não precisaram ser enviados

Figura 3. Predição em Rede usando dados de temperatura de um sensor S

4.2 Algoritmo Como decisão de projeto, foi definida que a estratégia de predição proposta seria implementada dentro do algoritmo do ADAGA (operador de agregação em rede proposto em [Brayner et al. 2006]). Portanto, o algoritmo proposto introduz a propriedade de predição em rede com precisão ajustável no algoritmo original do operador ADAGA.

O algoritmo proposto utiliza três áreas de armazenamento e é executado em oito estágios distintos. As áreas de armazenamento são as seguintes: (i) área de recepção, para armazenar pacotes recebidos; (ii) área de processamento, para armazenamento dos dados a serem processados; e (iii) área de envio, onde os pacotes a serem transmitidos são armazenados. Os estágios, representados em pseudocódigo na figura 4, são os seguintes: Estágio 1 – o primeiro laço (linha 1) é executado tantas vezes quanto forem definidas no valor da cláusula SCHEDULE da consulta. O segundo laço (linha 3) especifica que cada consulta deve ser executada enquanto esta for válida (considerando o tempo de validade da consulta definido na cláusula TIME WINDOW). O segundo laço ainda define quando devem ser realizados a recepção, o envio e a predição de dados, de forma que, a cada nova iteração deste laço, pacotes são recebidos (linha 15) e armazenados na área de recepção; se a consulta trabalhar com a possibilidade de predição (linha 16), então a predição é realizada (linha 17) e os pacotes armazenados na área de envio são enviados (linha 18); se não houver predição, os pacotes são transmitidos (linha 20), usando-se a estratégia original. O terceiro laço (linha 6) envolve as ações de sensoriamento e processamento de dados. O intervalo de tempo para cada nova iteração do terceiro laço é definido pelo valor da cláusula SEND INTERVAL; Estágio 2 – responsável pelo processamento da agregação em rede dos dados temporariamente armazenados na área de processamento. Estes dados podem ser provenientes da coleta de dados do meio ou da recepção de pacotes, enviados por outros nós-sensores; Estágio 3 – este estágio é responsável pelo monitoramento do uso de energia e memória no nó-sensor. Este estágio é disparado tanto pelo Estágio 1 (linha 13) como pelo Estágio 4 (linha 2); Estágio 4 – neste, os pacotes de dados recebidos são temporariamente armazenados na área de recepção (linha 3). Para cada pacote p1, na área de recepção de um dado nó n1, se p1 é originário de nós pertencentes ao mesmo grupo-sensor de n1 (linha 4), p1 é analisado e seus dados são armazenados na área de processamento (linha 9). Caso contrário, p1 é armazenado na área de envio (linha 12). Caso a consulta esteja utilizando predição (linha 6), o recebimento de um pacote de dados implica o recálculo dos coeficientes da equação da predição (linha 7); Estágio 5 – similar ao Estágio 8, é responsável por enviar pacotes a outros nós da rede. Este estágio é disparado pelo Estágio 1 (linha 20), no caso de consultas que não utilizam a predição de dados (linha 19); Estágio 6 – responsável por calcular os coeficientes da equação de regressão (linha 1) usados na predição do Estágio 7 (linha 2) e na Recepção de dados, no Estágio 4 (linha 7). Os coeficientes da predição alocam-se na área de processamento do sensor (linha 3); Estágio 7 – este estágio é responsável por realizar a predição futura de dados para o tempo de validade existente para a consulta, especificado na cláusula Time Window. Se ainda existir tempo para coleta dos dados (linha 1), é feito o cálculo dos coeficientes da equação de predição (linha 2) e estimam-se quantas predições precisam ser feitas, dividindo-se o tempo restante de Time Window pelo SendInterval (linha 4). As predições são então geradas em uma estrutura de dados que será armazenada na área de processamento; e Estágio 8 – é alternativa ao estágio 5, quando a consulta trabalha com predição de dados.

Neste estágio, os pacotes armazenados na área de envio são examinados e só serão transmitidos a outros nós da rede, caso o limite do threshold (veja descrição da fórmula apresentada na seção 3) tenha sido ultrapassado (linha 5). Para cada pacote p1 na área de envio (linha 1), considere os seguintes valores: c, o número de cópias de p1 (registrado no cabeçalho de p1); l, o número de cópias locais de p1, correntemente armazenadas em um dado nó n1 (linha 7); e nc = (c–l) (linha 9). Se nc > 1, p1 é enviado apenas para um dos nós-pais de n1, tomado aleatoriamente (linha 12). Porém, se nc = 1, p1 é enviado para todos os nós-pais de n1 (linha 15). Estágio 1: Adaga_Pred (Sensor n1, Consulta q)

Estágio 5: EnviarPacotes(Sensor n1)

1: Para i = 1 até nº. de execuções da consulta faça 2: inicialize o temporizador tempoTimeWindow; 3: Enquanto tempoTimeWindow < q.TimeWindow 4: inicialize o temporizador timerSendInterval; 5: n1.SenseInterval ← q.SenseInterval 6: Enquanto tempoSendInterval < q. SendInterval do 7: inicialize o temporizador timerSenseInterval; 8: Se tempoSenseInterval < q. SenseInterval então 9: d ← ColeteDadoAmbiente(); 10: inclua d em um pacote da área de processamento; 11: Fim Se 12: processarDado(); 13: monitorarRecursos(n1,q); 14: Fim Enquanto 15: ReceberPacotes(Sensor n1); 16: Se q possui threshold Então 17: Predicao (n1, q) 18: EnviarPacotesPredicao (n1) 19: Senão 20: EnviarPacotes(Sensor n1); 21: Fim Se 17: Fim Enquanto 18: Fim Para

1: Para cada pacote na área de envio Faça 2: p1 ← carregar pacote da área de envio; 3: c ← número de cópias de p1 no seu cabeçalho; 4: l ← carregar o número de cópias locais de p1; 5: descartar l –1 cópias de p1; 6: nc ← c - l; 7: registrar nc no cabeçalho da cópia de p1 mantida; 8: Se nc > 1 Então 9: n2 ← nó pai de n1 escolhido aleatoriamente; 10: envie p1 para s´; 11: Senão 12: envie p1 para todos os nós pai de n1; 13: Fim Se 14: descarte p1 da área de envio; 15: Fim Para

Estágio 2: ProcessarDado() 1: ds1 ← carregar dados da área de processamento; 2: ds2 ← agg(ds1);//agregar dados do conjunto de dados ds1 3: armazenar ds2 na área de processamento;

Estágio 3: MonitorarRecursos(Sensor n1, Consulta q) 1: 2: 3: 4: 5: 6: 7:

x1 ← s.carregueEnergiaDisponivel (); x2 ← s.carregueMemóriaDisponivel(); v ← q.SendInterval; t ← q.TimeWindow; n1 ← q.SenseInterval; n1.SendInterval ← adapteSendInterval(x1,v,t); n1.SenseInterval ← adapteSenseInterval(x2,s,v);

Estágio 4: ReceberPacotes(Sensor n1, Consulta q) 1: Para cada pacote na área de recepção Faça 2: monitorarRecursos(n1,q); 3: p1 ← carregar pacote da área de recepção; 4: Se grupo sensor de p1 = n1.grupoSensor Então 5: Se número de cópias no cabeçalho de p1 =1 Então 6: Se q possui threshold Então 7: Coeficientes (n1); //coeficientes de n1 8: Fim Se 9: área de processamento ← p1; 10: Fim Se 11: Senão 12: área de envio ← p1; 13: Fim Se 14: Fim Para

Estágio 6: Coeficientes(Sensor n1) 1: calcular os coeficientes a e b da equação de regressão; 2: cSn1 ← a e b; //coeficientes 3: área de processamento ← cSn1;

Estágio 7: Predicao(Sensor n1, Consulta q) 1: Se tempoTimeWindow < q.TimeWindow Então 2: Coeficientes (n1); // calcula os coeficientes a e b de n1 3: t ← 0; 4: x ← tempoTimeWindow / tempoSendWindow; 5: Para i = 1 até x Faça 6: t ← t + tempoSendWindow; 7: pred[i] ← cSn1[a] + (cSn1[b] * t); 8: Fim Para 9: área de processamento ← pred; 10: Fim Se

Estágio 8: EnviarPacotesPredicao(Sensor n1) 1: Para cada pacote na área de envio Faça 2: p1 ← carregar pacote da área de envio; 3: pred ← Carregar predição da área de processamento; 4: x ← tempoTimeWindow / tempoSendWindow; 5: Se (q.threshold) < (100(p1 – pred[x])/ p1) Então 6: c ← número de cópias de p1 no seu cabeçalho; 7: l ← carregar o número de cópias locais de p1; 8: descartar l –1 cópias de p1; 9: nc ← c - l; 10: registrar nc no cabeçalho da cópia de p1 mantida; 11: Se nc > 1 Então 12: n2 ← nó pai de n1 escolhido aleatoriamente; 13: envie p1 para s´; 14: Senão 15: envie p1 para todos os nós pai de n1; 16: Fim Se 17: Fim Se 18: descarte p1 da área de envio; 19: Fim Para

Figura 4. Algoritmo proposto

5. Testes Realizados Nesta seção, apresentam-se os resultados da estratégia de predição em rede, comprovando sua eficiência na redução do consumo de energia nas redes de sensores

sem fio. A quantidade de informação coletada pelos nós é comparada à quantidade de informação que foi enviada na rede, usando-se a predição, de forma a se poder verificar a qualidade da estratégia adotada. Para a realização dos testes, foi criado um simulador de redes de sensores, em linguagem de programação Java, que executou em uma máquina Core 2 Duo com 2GB de memória RAM. O simulador permite a configuração da disponibilidade de energia e memória para um conjunto de nós sensores. Nos experimentos, assume-se que todos os nós estão corretamente sincronizados, utilizando esta definição para a agregação e para a predição em rede. De acordo com a natureza da predição em rede, as funções de predição dos nós sensores não precisam ser recalculadas na maior parte do tempo. Daí o fato de serem considerados apenas os custos de comunicação e coleta de dados, nos experimentos. A consulta utilizada na geração dos resultados pode ser vista na Figura 2. Com a adição da cláusula de Threshold, a consulta foi modificada para suportar a predição, como visto na Figura 5. Nela, o valor th corresponde ao percentual aceitável para que a predição seja aceitável. Nesta consulta, seu valor variou para valores inteiros entre 1 e 10%. Primeiramente, avaliou-se a estratégia de predição em relação à influência do parâmetro de threshold sobre os dados considerados pela predição, desconsiderando restrições de recursos para todos os sensores (Figura 7) e depois para sensores individualmente (Figura 8). Também se verificou o consumo de energia na rede, através da relação entre consumo de memória e consumo de energia, dos nós sensores (Figura 9). SELECT t.Sensor, avg(t.ValorColetado) FROM Temperature as t GROUP BY t.Sensor TIME WINDOW 90000 SEND INTERVAL 3000 SENSE INTERVAL 10 SCHEDULE 1 ‘01-Feb-08 00:00:00’ THRESHOLD th;

Figura 5. Consulta utilizada para avaliação dos resultados produzidos

Foram realizados experimentos, fazendo uso do simulador, sobre um conjunto de dados reais (seção 5.1) e também sobre um conjunto de dados sintéticos (seção 5.2) de temperatura. Os resultados obtidos nas figuras 7, 8 e 10, referenciam dados da proposta (agregação e predição em rede). Já os resultados das figuras 9 e 11, comparam três estratégias distintas: (i) ingênua: dados sem agregação e sem predição; (ii) ADAGA: somente agregação; e (iii) estratégia proposta, admitindo agregação e predição em rede. 5.1 Dados Reais Foram usados valores reais da temperatura ambiente do Estado do Ceará no ano de 2007, obtidos junto à Funceme – Fundação Cearense de Meteorologia e Recursos Hídricos. As leituras foram feitas por um conjunto de 26 sensores dispostos de acordo com a Figura 6, onde cada sensor realizou 24 leituras diárias, em um intervalo de 46 dias, perfazendo 1.104 leituras por sensor, totalizando 28.704 leituras de dados. As simulações realizadas consideram a disposição dos sensores na Figura 6 como sendo uma rede de sensores sem fio. Para preservar a correlação de tempo e espaço, os dados de uma mesma fonte original são diretamente atribuídos como dados de um único nó sensor, sendo usados exatamente como vieram das fontes.

Figura 6. Sensores distribuídos pela região de coleta de dados

A Figura 7 apresenta o percentual de predições realizadas – taxa de acerto – sobre todos os sensores. Pode-se observar que a quantidade de dados válidos para a predição cresce conforme o incremento da cláusula de threshold, confirmando uma situação já esperada. Ao considerar o threshold a 0%, não foram obtidos dados aceitáveis pela predição, ou seja, precisa-se de uma tolerância mínima de 1% para obter alguma predição válida. A variação máxima utilizada foi de 10%, pois uma tolerância superior a esta pode acarretar dados tão distantes da realidade que não valeria à pena para o modelo proposto. Porém, valores maiores podem ser utilizados, dependendo da aplicação.

Figura 7. Taxa de Acerto x Threshold: todos os sensores

Na figura 8, são apresentadas as taxas de acerto obtidas pela predição de alguns sensores, individualmente. Está sendo considerado um conjunto de 1.104 leituras de dados do ambiente, realizadas por cada um deles. Observa-se que para um threshold de 5% já se obtém uma taxa de acerto superior a 20%.

Figura 8. Taxa de Acerto x Threshold: Exemplos para alguns sensores

Outra análise essencial para avaliar a estratégia proposta refere-se ao consumo de energia de cada sensor e de toda a rede. O modelo utilizado para tal análise considera o consumo de 75 nJ por bit transmitido, 50 nJ por bit recebido e um consumo de 125 nJ/bit para sensoriamento e processamento. Consideram-se cada pacote de dados, para a agregação, ocupando 8 bytes de espaço de memória. Na figura 9, compara-se o consumo de energia dos nós sensores, para a agregação e predição em rede, em relação ao ADAGA [Brayner et al. 2006] e em relação a uma estratégia que não admite o uso de agregação nem de predição (estratégia ingênua). Variando a predição para três valores de threshold: 1%, 5% e 10%, observa-se que a estratégia de predição em rede apresenta-se mais eficiente quanto ao consumo de energia pelos nós sensores. Mesmo com um threshold mínimo de 1%. Aumentando o threshold a 5% e a 10%, a redução do consumo de energia torna-se mais significativa ainda, para a predição em rede. Pode-se concluir disto, que o aumento do threshold influencia diretamente na redução do consumo de energia da rede. A Figura 9 também mostra que não há uma tendência entre a predição em rede e as outras estratégias, onde elas possam convergir para uma mesma taxa de redução de consumo de energia. Logo, conclui-se que a predição em rede aliada à agregação do ADAGA aperfeiçoa o desempenho deste em relação ao consumo de energia, aumentando o tempo de vida da RSSF.

Figura 9. Consumo de energia no processamento dos valores da média da temperatura

5.2 Dados Sintéticos Foi desenvolvido um conjunto de dados sintéticos, usando IBM data generator [IBM 2008]. O conjunto de dados inclui 300.000 registros de temperatura, distribuídos uniformemente por 30 sensores diferentes. Desta forma, a amostra contém 1.000 leituras de dados para cada sensor. Fazendo uso dos dados sintéticos, foram produzidos os resultados apresentados nas Figuras 10 e 11. Na figura 10, observa-se resultado semelhante ao da Figura 7, porém houve uma melhora dos percentuais de acerto, devido aos dados produzidos pela função.

Figura 10. Taxa de Acerto x Threshold: Dados Sintéticos

A figura 11 comprova que o ganho de energia com a utilização da predição, se manteve para os dados sintéticos, com resultados ainda melhores que os apresentados com os dados reais. Observando os valores máximos da predição para os dois conjuntos de dados, pode-se ver que enquanto o valor máximo de energia utilizado para a predição com threshold a 5%, nos dados reais, foi de 44,2 x 105, nos dados sintéticos este valor foi de 36,5 x 105. Importante observar que o ADAGA e a estratégia ingênua, praticamente não apresentaram variação.

Figura 11. Consumo de energia no processamento dos valores da média da temperatura: Dados Sintéticos

Os resultados mostram que a estratégia proposta é um mecanismo eficiente de redução do consumo de energia para as redes de sensores sem fio, superando a estratégia de agregação sem predição de dados futuros. Estes resultados foram obtidos sobre dados de temperatura, reconhecidamente mais bem comportados que outros tipos de dados, como luminosidade e pluviosidade, que possuem comportamento bem menos previsível. Esta característica remete a uma oportunidade de ampliação da proposta, com testes futuros utilizando estes dados.

6. Conclusão Neste artigo, foi apresentada uma estratégia de agregação e predição em rede com precisão ajustável, para redes de sensores sem fio. Os resultados experimentais mostram que a estratégia proposta pode reduzir consideravelmente o número de mensagens enviadas e recebidas por cada nó sensor. A redução no envio e recebimento de mensagens, implica diretamente em uma redução no consumo de energia, aumentando o tempo de vida da RSSF. Para os dados de temperatura utilizados nos testes, utilizando um threshold de 5% (aproximadamente 1ºC), foi obtida uma redução no consumo de energia superior a 30%. Aumentando o limite de diferença aceitável entre o valor da predição e o dado real coletado do ambiente, para 10% (aproximadamente 2ºC), a estratégia proposta alcança uma economia de 67% no consumo de energia da RSSF.

7. Referência Bibliográfica Adler, R., Buonadonna, P., Chabra, J., Flanigan, M., Krishnamurthy, L., Kushalnagar, N., Nachman, L., e Yarvis, M. (2005). “Design and deployment of industrial sensor networks: Experiences from the north sea and a semiconductor plant”. In SenSys ’05: Proceedings of the 3rd international conference on Embedded networked sensor systems, pages 64–75, New York, NY, USA, 2005. ACM Press. Bonnet, P., Gehrke, J., e Seshadri, P. (2001) “Towards sensor database systems”. In Proceedings of the Second International Conference on Mobile Data Management. Hong Kong, January 2001.

Brayner, A., Lopes, A., Meira, D., Vasconcelos, R., e Menezes, R. (2006). “ADAGA - ADaptive AGgregation Algorithm for Sensor Networks”, In 21st Brazilian Symposium on Databases, October 16-20 2006. Brayner, A., Lopes, A., Meira, D., Vasconcelos, R., e Menezes, R. (2007). “Toward adaptive query processing in wireless sensor networks”. In Signal Processing Journal, Elsevier vol. 87 no. 12 p.2911-2933. Emekci, F., Yu, H., Agrawal, D., Abbadi, e Amr E. (2003). “Energy-conscious data aggregation over large-scale sensor networks”. University of California, Santa Barbara. Tech Report 2003-32. Deligiannakis, A., Kotidis, Y., e Roussopoulos, N. (2006). “Processing approximate aggregate queries in wireless sensor networks”, In Information Systems Journal, Volume 31(8), p.770792, December 2006. Deshpande, A., e Madden, S. (2006) “MauveDB: Supporting Model-based User Views in Database Systems”. In ACM SIGMOD 2006 International Conference Management of Data, ACM Press, 2006, pp. 73–84. Desnoyers, P., Ganesan, D., Li, H., e Shenoy, P. (2005). “PRESTO: A Predictive Storage Architecture for Sensor Networks”, In Tenth Workshop on Hot Topics in Operating Systems (HotOS X), Santa Fe, New Mexico, June 2005. IBM Almaden Research Center, (2008) “Synthetic data generation code for associations and sequential patterns”, disponível em: http://www.almaden.ibm.com/cs/projects/iis/hdb/Projects/data_mining/datasets/syndata.html# assocSynData. Kumar, V., Cooper, Brian F., e Navathe, S. B. (2004). “Predictive Filtering: A Learning-Based Approach to Data Stream Filtering”. In 1st international workshop on Data management for sensor networks (DMNS 2004: 17-23): in conjunction with VLDB 2004. Toronto, Canada. Madden, S., Franklin, M.J., Hellerstein, J.M., e Hong, W. (2002). “TAG: A Tiny Aggregation Service for Ad-Hoc Sensor Networks”, In Proceedings of the 5th Symposium on Operating System Design and Implementation (OSDI 2002), Boston/Massachusetts, Dec. 2002. Madden, S., Franklin, M.J., Hellerstein, J.M., e Hong, W. (2003). “The Design of an Acquisitional Query processor for Sensor Networks”. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003, pp 491-502. Madden, S., Franklin, M.J., Hellerstein, J.M., e Hong, W. (2008). “TinyDB web Page”. http://telegraph.cs.berkeley.edu/tinydb, acessado em 01 de Março de 2008. Patt-Shamir, B. (2007). “A note on efficient aggregate queries in sensor networks”. In Theoretical Computer Science 2007, v.370 n.1-3, p.254-264. Polastre, J., Szewczyk, R., Mainwaring, A., Culler, D., e Anderson, J. (2002). “Wireless sensor networks for habitat monitoring”. In ACM International Workshop on Wireless Sensor Networks and Applications (WSNA 2002), Atlanta, Georgia, September 2002. Tilak, S., Abu-Ghazaleh, N. B., e Heinzelman W. (2002). “A taxonomy of wireless micro-sensor network models”. Mobile Computing and Communication Review, 6(2), april 2002. Wun, A., Petrovi, M., e Jacobsen, H. (2007). “A system for semantic data fusion in sensor networks”, In Proceedings of the 2007 inaugural international conference on Distributed event-based systems (DEBS07), pages 75-79, June 2007, Toronto, Ontario, Canada. Yao, Y. e Gehrke, J. (2002). “The cougar approach to in-network query processing in sensor networks”. In Sigmod 2002, Volume 31 (3). September 2002.